Art of Problem Solving
AoPS Online
Math texts, online classes, and more
for students in grades 5-12.
Visit AoPS Online ‚
Books for Grades 5-12 Online Courses
Beast Academy
Engaging math books and online learning
for students ages 6-13.
Visit Beast Academy ‚
Books for Ages 6-13 Beast Academy Online
AoPS Academy
Small live classes for advanced math
and language arts learners in grades 2-12.
Visit AoPS Academy ‚
Find a Physical Campus Visit the Virtual Campus

Difference between revisions of "Divisibility rules/Rule for 11 proof"

(→‎Proof)
(Undo revision 215833 by Marianasinta (talk))
(Tag: Undo)
 
(10 intermediate revisions by 6 users not shown)
Line 4: Line 4:
 
''An understanding of [[Introduction to modular arithmetic | basic modular arithmetic]] is necessary for this proof.''
 
''An understanding of [[Introduction to modular arithmetic | basic modular arithmetic]] is necessary for this proof.''
  
−
Let <math>N = a_na_{n-1}\cdots a_1a_0</math> where the <math>a_i</math> are [[base numbers | base-ten]] numbers.  Then <math>N = 10^n a_n + 10^{n-1} a_{n-1} + \cdots + 10 a_1 + a_0.</math>
+
Let <math>N = a_ka_{k-1}\cdots a_1a_0</math> where the <math>a_i</math> are [[base numbers | base-ten]] numbers.  Then <math>N = 10^k a_k + 10^{k-1} a_{k-1} + \cdots + 10 a_1 + a_0.</math>
  
−
Note that <math>10\equiv -1\pmod{11}</math>.  Thus <center><math> 10^n a_n + 10^{n-1} a_{n-1} + \cdots + 10a_1 + a_0 \equiv (-1)^n a_n + (-1)^{n-1} a_{n-1} + \cdots -a_1 + a_0. </math></center>
+
Note that <math>10\equiv -1\pmod{11}</math>.  Thus <math> 10^k a_k\!\! +\!\!10^{k-1} a_{k-1}\! +\! \cdots + 10a_1 + a_0 \equiv (-1)^k a_k + (-1)^{k-1} a_{k-1} + \cdots -a_1 + a_0 \pmod {11}. </math>
  
 
This is the alternating sum of the digits of <math>N</math>, which is what we wanted.
 
This is the alternating sum of the digits of <math>N</math>, which is what we wanted.
 +
 +
***
 +
Here is another way that doesn't require knowledge of modular arithmetic. Suppose we have a 3-digit number that is expressed in the form:
 +
<math>100a+10b+c</math><br />
 +
we then can transpose this into:
 +
<math>99a+a+11b-b+c</math><br />
 +
and that equals:
 +
<math>(99a+11b)+(a-b+c)</math><br />
 +
which equals
 +
<math>11(9a+b)+(a-b+c)</math><br />
 +
Since the first addend, <math>11(9a+b)</math> will always be divisible by 11, we just need to make sure that <math>(a-b+c)</math> is divisible by 11.
 +
 +
You can use this for any number. Here it is again, with an even-numbered digit number:
 +
 +
<math>1000a+100b+10c+d</math><br />
 +
<math>1001a-a+99b+b+11c-c+d</math><br />
 +
<math>(1001a+99b+11c)-(a-b+c-d)</math><br />
 +
<math>11(91a+9b+c)-(a-b+c-d)</math><br />
 +
So you just need to check <math>(a-b+c-d)</math> for divisibility with 11.
  
 
== See also ==
 
== See also ==
 
* [[Divisibility rules | Back to divisibility rules]]
 
* [[Divisibility rules | Back to divisibility rules]]
 +
[[Category:Divisibility Rules]]

Latest revision as of 14:23, 8 June 2024

A number $N$ is divisible by 11 if the alternating sum of the digits is divisible by 11.

Proof

An understanding of basic modular arithmetic is necessary for this proof.

Let $N = a_ka_{k-1}\cdots a_1a_0$ where the $a_i$ are base-ten numbers. Then $N = 10^k a_k + 10^{k-1} a_{k-1} + \cdots + 10 a_1 + a_0.$

Note that $10\equiv -1\pmod{11}$. Thus $10^k a_k\!\! +\!\!10^{k-1} a_{k-1}\! +\! \cdots + 10a_1 + a_0 \equiv (-1)^k a_k + (-1)^{k-1} a_{k-1} + \cdots -a_1 + a_0 \pmod {11}.$

This is the alternating sum of the digits of $N$, which is what we wanted.

Here is another way that doesn't require knowledge of modular arithmetic. Suppose we have a 3-digit number that is expressed in the form: $100a+10b+c$
we then can transpose this into: $99a+a+11b-b+c$
and that equals: $(99a+11b)+(a-b+c)$
which equals $11(9a+b)+(a-b+c)$
Since the first addend, $11(9a+b)$ will always be divisible by 11, we just need to make sure that $(a-b+c)$ is divisible by 11.

You can use this for any number. Here it is again, with an even-numbered digit number:

$1000a+100b+10c+d$
$1001a-a+99b+b+11c-c+d$
$(1001a+99b+11c)-(a-b+c-d)$
$11(91a+9b+c)-(a-b+c-d)$
So you just need to check $(a-b+c-d)$ for divisibility with 11.

See also

Retrieved from "https://artofproblemsolving.com/wiki/index.php?title=Divisibility_rules/Rule_for_11_proof&oldid=220232"