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 1 for 7 proof"

m (→‎Proof)
m (Fixed)
 
(One intermediate revision by the same user not shown)
Line 2: Line 2:
 
''This is based on [[Divisibility_rules/Rule_for_11_proof | divisibility by 11 rule ]]''
 
''This is based on [[Divisibility_rules/Rule_for_11_proof | divisibility by 11 rule ]]''
  
−
Assume N has 3k digits, otherwise add zeros to the left.
+
Assume <math>N</math> has <math>3k</math> digits, otherwise add zeros to the left.
 
[[Without_loss_of_generality | WLOG ]] let <math>N = a_{3k-1}a_{3k-2}a_{3k-3}\cdots a_8a_7a_6a_5a_4a_3a_2a_1a_0</math> where the <math>a_i</math> are [[base numbers | base-ten]] numbers.  
 
[[Without_loss_of_generality | WLOG ]] let <math>N = a_{3k-1}a_{3k-2}a_{3k-3}\cdots a_8a_7a_6a_5a_4a_3a_2a_1a_0</math> where the <math>a_i</math> are [[base numbers | base-ten]] numbers.  
−
Then <math>N = 10^{3k-1} a_{3k-1} + 10^{3k-2} a_{3k-2} + 10^{3k-3} a_{3k-3} \cdots + 10^8 a_8 + 10^7 a_7 + 10^6 a_6 + 10^5 a_5 + 10^4 a_4 + 10^3 a_3 + 10^2 a_2 + 10 a_1 + a_0.</math>
+
Then <cmath>N = 10^{3k-1} a_{3k-1} + 10^{3k-2} a_{3k-2} + 10^{3k-3} a_{3k-3} \cdots + 10^8 a_8 + 10^7 a_7 + 10^6 a_6 + 10^5 a_5 + 10^4 a_4 + 10^3 a_3 + 10^2 a_2 + 10 a_1 + a_0</cmath>
−
<math>= 1000^{k-1} (100 a_{3k-1} + 10 a_{3k-2} + a_{3k-3}) \cdots + 1000^2 (100 a_8 + 10 a_7 + a_6) + 1000 (100 a_5 + 10 a_4 + a_3) + (100 a_2 + 10 a_1 + a_0).</math>
+
<cmath>= 1000^{k-1} (100 a_{3k-1} + 10 a_{3k-2} + a_{3k-3}) \cdots + 1000^2 (100 a_8 + 10 a_7 + a_6) + 1000 (100 a_5 + 10 a_4 + a_3) + (100 a_2 + 10 a_1 + a_0).</cmath>
  
 
Rewriting or partitioning <math>N</math> into 3 digit numbers (<math>a_{3k-1}a_{3k-2}a_{3k-3}\cdots a_8a_7a_6 a_5a_4a_3 a_2a_1a_0</math>).
 
Rewriting or partitioning <math>N</math> into 3 digit numbers (<math>a_{3k-1}a_{3k-2}a_{3k-3}\cdots a_8a_7a_6 a_5a_4a_3 a_2a_1a_0</math>).

Latest revision as of 15:07, 2 October 2024

Proof

This is based on divisibility by 11 rule

Assume $N$ has $3k$ digits, otherwise add zeros to the left. WLOG let $N = a_{3k-1}a_{3k-2}a_{3k-3}\cdots a_8a_7a_6a_5a_4a_3a_2a_1a_0$ where the $a_i$ are base-ten numbers. Then \[N = 10^{3k-1} a_{3k-1} + 10^{3k-2} a_{3k-2} + 10^{3k-3} a_{3k-3} \cdots + 10^8 a_8 + 10^7 a_7 + 10^6 a_6 + 10^5 a_5 + 10^4 a_4 + 10^3 a_3 + 10^2 a_2 + 10 a_1 + a_0\] \[= 1000^{k-1} (100 a_{3k-1} + 10 a_{3k-2} + a_{3k-3}) \cdots + 1000^2 (100 a_8 + 10 a_7 + a_6) + 1000 (100 a_5 + 10 a_4 + a_3) + (100 a_2 + 10 a_1 + a_0).\]

Rewriting or partitioning $N$ into 3 digit numbers ($a_{3k-1}a_{3k-2}a_{3k-3}\cdots a_8a_7a_6 a_5a_4a_3 a_2a_1a_0$). $N = 1000^{k-1} (a_{3k-1}a_{3k-2}a_{3k-3}) \cdots + 1000^2 (a_8a_7a_6) + 1000 (a_5a_4a_3) + (a_2a_1a_0).\\ \equiv (-1)^{k-1} (a_{3k-1}a_{3k-2}a_{3k-3}) \cdots + (-1)^2 (a_8a_7a_6) - (a_5a_4a_3) + (a_2a_1a_0) \pmod {7}, \text{since} 1000\equiv -1\pmod{7}$


This is the alternating sum of groups of 3 digit numbers of $N$, which is what we wanted.

See also

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