Keep a divisibility statement in an explicit integer-multiple form.
Notes and key methods
To prove d divides an expression F(n), aim to write F(n)=dM for an integer M. In an induction step, express F(k+1) in terms of F(k) plus a remainder that is visibly divisible by d.
For example, \(a^{k+1}-b^{k+1}=a(a^k-b^k)+(a-b)b^k\). With integer a,b this shows the factor a−b persists from one exponent to the next.
Check the conditions
The divisor is a nonzero integer.
The quotient introduced in a divisibility proof is an integer.
Three worked examples
Example 1 · Induction and divisibility
Work with the integer powers \(6^n-3^n\).
Find \(\displaystyle \frac{6^{4}- 3^{4}}{3}\).
Find the difference at \(\displaystyle n=1\).
Find the quotient at \(\displaystyle n=5\).
Find the integer remainder term \(\displaystyle 3^4\) in the successor quotient relation.
Show the reasoning
(a)
\(\displaystyle \frac{6^{4}- 3^{4}}{3}= 405\)
Answer: \(405\).
(b)
\(6-3=3\)
Answer: \(3\).
(c)
\(\displaystyle \frac{6^{5}- 3^{5}}{3}= 2511\)
Answer: \(2511\).
(d)
\(3^{4}=81\)
Answer: \(81\).
Example 2 · Induction and divisibility
Work with the integer powers \(8^n-4^n\).
Find \(\displaystyle \frac{8^{5}- 4^{5}}{4}\).
Find the difference at \(\displaystyle n=1\).
Find the quotient at \(\displaystyle n=6\).
Find the integer remainder term \(\displaystyle 4^5\) in the successor quotient relation.
Show the reasoning
(a)
\(\displaystyle \frac{8^{5}- 4^{5}}{4}= 7936\)
Answer: \(7936\).
(b)
\(8-4=4\)
Answer: \(4\).
(c)
\(\displaystyle \frac{8^{6}- 4^{6}}{4}= 64512\)
Answer: \(64512\).
(d)
\(4^{5}=1024\)
Answer: \(1024\).
Example 3 · Induction and divisibility
Work with the integer powers \(7^n-5^n\).
Find \(\displaystyle \frac{7^{3}- 5^{3}}{2}\).
Find the difference at \(\displaystyle n=1\).
Find the quotient at \(\displaystyle n=4\).
Find the integer remainder term \(\displaystyle 5^3\) in the successor quotient relation.
Show the reasoning
(a)
\(\displaystyle \frac{7^{3}- 5^{3}}{2}= 109\)
Answer: \(109\).
(b)
\(7-5=2\)
Answer: \(2\).
(c)
\(\displaystyle \frac{7^{4}- 5^{4}}{2}= 888\)
Answer: \(888\).
(d)
\(5^{3}=125\)
Answer: \(125\).
Common mistakes
A decimal approximation cannot prove exact divisibility.