Chapter
Theory
LTE, lifting the exponent, gives the exact exponent of a prime \(p\) in a difference of powers. It is especially powerful when \(p\mid a-b\) or \(p\mid a+b\), and the expression has the form \(a^n-b^n\).
Basic form: if \(p\) is an odd prime, \(p\mid a-b\), and \(p\nmid ab\), then \(v_p(a^n-b^n)=v_p(a-b)+v_p(n)\). If \(p\) is odd, \(p\mid a+b\), \(n\) is even, and \(p\nmid ab\), then \(v_p(a^n-b^n)=v_p(a+b)+v_p(n)\). For \(p=2\): if \(a,b\) are odd and \(n\) is even, then \(v_2(a^n-b^n)=v_2(a-b)+v_2(a+b)+v_2(n)-1\).
Use LTE when \(a^n-b^n\), transformed \(a^n+b^n\), large exponents, conditions \(p^k\mid a^n-b^n\), or requests to find all \(n\) with a sufficiently large prime exponent appear.
Check whether the prime \(p\) divides \(a-b\) or \(a+b\). If it does, ordinary factorisation often gives only the first step, while LTE gives the exact exponent immediately.
Do not apply the odd-prime formula to \(p=2\). In the \(p\mid a+b\) case for \(a^n-b^n\), the exponent \(n\) must be even. Also check \(p\nmid a\) and \(p\nmid b\); otherwise the formula may fail.
1. Which prime \(p\) is counted? 2. Does it divide \(a-b\) or \(a+b\)? 3. Is the exponent even when using \(a+b\)? 4. Does \(p\) avoid the bases? 5. Has the condition \(p^k\mid\) been converted into an inequality for \(v_p\)?
Examples
First direct application of LTE.
Problem. Find \(v_3(10^{2025}-1)\).
Since \(3\mid10-1\), LTE gives \(v_3(10^{2025}-1)=v_3(9)+v_3(2025)=2+4=6\).
Comment. Without LTE, the factorisation would be very long.
This shows the case \(p\mid a+b\).
Problem. Find \(v_3(2^{100}-1)\).
Here \(3\mid2+1\), and the exponent \(100\) is even. Hence \(v_3(2^{100}-1)=v_3(2+1)+v_3(100)=1+0=1\).
Comment. The exponent being even is essential.
A separate formula for twos.
Problem. Find \(v_2(3^{100}-1)\).
For odd \(3\) and \(1\), with even \(100\): \(v_2(3^{100}-1)=v_2(3-1)+v_2(3+1)+v_2(100)-1=1+2+2-1=4\).
Comment. The formula for \(2\) differs from the odd-prime case.
This shows how LTE solves divisibility.
Problem. Find all \(n\) such that \(7^3\mid8^n-1\).
Since \(7\mid8-1\), \(v_7(8^n-1)=v_7(7)+v_7(n)=1+v_7(n)\). We need \(1+v_7(n)\ge3\), so \(v_7(n)\ge2\). Answer: \(49\mid n\).
Comment. A prime-power condition became a condition on \(n\).
This shows the transition from \(p^k\) to \(v_p\).
Problem. Find the largest \(k\) such that \(9^k\mid10^{2025}-1\).
From Example 1, \(v_3(10^{2025}-1)=6\). Since \(9^k=3^{2k}\), we need \(2k\le6\). Answer: \(k=3\).
Comment. First count the prime exponent, then account for the composite base.
This prepares for answers involving \(v_p(n)\).
Problem. Find \(v_5(11^n-1)\).
Since \(5\mid11-1\), LTE gives \(v_5(11^n-1)=v_5(10)+v_5(n)=1+v_5(n)\).
Comment. The answer depends on the exponent \(n\).
This teaches finding all \(n\).
Problem. Find all \(n\) such that \(7^n\mid8^n-1\).
By LTE, \(v_7(8^n-1)=1+v_7(n)\). We need \(1+v_7(n)\ge n\). For \(n=1\), it holds. For \(n\ge2\), \(v_7(n)\le \log_7 n
Comment. The last step compares the growth of \(n\) and \(v_7(n)\).
An olympiad template for \(p=2\).
Problem. Prove that for \(m\ge1\), \(v_2(3^{2^m}-1)=m+2\).
Apply the formula for \(2\): \(v_2(3^{2^m}-1)=v_2(3-1)+v_2(3+1)+v_2(2^m)-1=1+2+m-1=m+2\).
Comment. This is a very common subproblem in stronger examples.
Problems
Find \(v_3(10^{2025}-1)\).
Use \(3\mid10-1\).
By LTE, \(v_3(10^{2025}-1)=v_3(10-1)+v_3(2025)=v_3(9)+4=2+4=6\).
Find \(v_7(8^{100}-1)\).
\(7\mid8-1\).
By LTE, \(v_7(8^{100}-1)=v_7(7)+v_7(100)=1+0=1\).
Find \(v_5(6^{50}-1)\).
\(5\mid6-1\).
\(v_5(6^{50}-1)=v_5(5)+v_5(50)=1+2=3\).
Find \(v_3(2^{100}-1)\).
\(3\mid2+1\), and \(100\) is even.
Since \(3\mid2+1\) and \(100\) is even, \(v_3(2^{100}-1)=v_3(3)+v_3(100)=1\).
Find \(v_2(3^{100}-1)\).
Use the formula for \(p=2\).
\(v_2(3^{100}-1)=v_2(2)+v_2(4)+v_2(100)-1=1+2+2-1=4\).
Find all positive integers \(n\) such that \(7^3\mid8^n-1\).
Compute \(v_7(8^n-1)\).
\(v_7(8^n-1)=1+v_7(n)\). We need \(1+v_7(n)\ge3\), i.e. \(v_7(n)\ge2\). Answer: all \(n\) divisible by \(49\).
Find the largest \(k\) such that \(9^k\mid10^{2025}-1\).
First find \(v_3\).
From Problem 1, \(v_3(10^{2025}-1)=6\). Since \(9^k=3^{2k}\), \(2k\le6\), hence \(k=3\).
Find \(v_5(11^n-1)\).
\(5\mid11-1\).
By LTE, \(v_5(11^n-1)=v_5(10)+v_5(n)=1+v_5(n)\).
Find \(v_3(4^n-1)\).
\(3\mid4-1\).
\(v_3(4^n-1)=v_3(3)+v_3(n)=1+v_3(n)\).
Find \(v_3(5^{2n}-1)\).
\(3\mid5+1\), and the exponent \(2n\) is even.
By the \(a+b\) case, \(v_3(5^{2n}-1)=v_3(6)+v_3(2n)=1+v_3(n)\).
Find \(v_2(5^n-1)\) depending on the parity of \(n\).
For odd \(n\), use the \(5-1\) factor; for even \(n\), use the formula for \(2\).
If \(n\) is odd, \(v_2(5^n-1)=v_2(5-1)=2\). If \(n\) is even, \(v_2(5^n-1)=v_2(4)+v_2(6)+v_2(n)-1=2+1+v_2(n)-1=2+v_2(n)\).
Find all \(n\) such that \(16\mid3^n-1\).
Split by parity of \(n\).
If \(n\) is odd, \(v_2(3^n-1)=v_2(2)=1\), not enough. If \(n\) is even, then \(v_2(3^n-1)=v_2(2)+v_2(4)+v_2(n)-1=2+v_2(n)\). We need \(2+v_2(n)\ge4\), so \(v_2(n)\ge2\). Answer: \(4\mid n\).
Find all \(n\) such that \(3^5\mid4^n-1\).
Use \(v_3(4^n-1)=1+v_3(n)\).
We need \(1+v_3(n)\ge5\), i.e. \(v_3(n)\ge4\). Answer: \(81\mid n\).
Let \(p\) be an odd prime, \(p\mid a-b\), \(p\nmid ab\). Prove that \(p^r\mid a^{p^{r-1}}-b^{p^{r-1}}\) for every \(r\ge1\).
Apply LTE to the exponent \(p^{r-1}\).
By LTE, \(v_p(a^{p^{r-1}}-b^{p^{r-1}})=v_p(a-b)+v_p(p^{r-1})\). Since \(p\mid a-b\), the first term is at least \(1\), and the second equals \(r-1\). The total exponent is at least \(r\), so divisibility by \(p^r\) follows.
Find the largest \(k\) such that \(3^k\mid2^{2n}-1\).
Replace \(2^{2n}\) by \(4^n\).
\(2^{2n}-1=4^n-1\). Since \(3\mid4-1\), \(v_3(4^n-1)=1+v_3(n)\). Therefore \(k=1+v_3(n)\).
Find \(v_3(13^n-1)\).
\(3\mid13-1\).
By LTE, \(v_3(13^n-1)=v_3(12)+v_3(n)=1+v_3(n)\).
Find all positive integers \(n\) such that \(3^n\mid10^n-1\).
Compare \(n\) with \(v_3(10^n-1)\).
By LTE, \(v_3(10^n-1)=v_3(9)+v_3(n)=2+v_3(n)\). We need \(2+v_3(n)\ge n\). The values \(n=1,2,3\) work. If \(n\ge4\), then \(2+v_3(n)
Find all positive integers \(n\) such that \(7^n\mid8^n-1\).
Use \(v_7(8^n-1)=1+v_7(n)\).
We need \(1+v_7(n)\ge n\). For \(n=1\), the condition holds. If \(n\ge2\), then \(v_7(n)\le \log_7 n
Let \(p\) be an odd prime, \(p\mid a-b\), \(p^2\nmid a-b\), and \(p\nmid ab\). Prove that \(p^r\mid a^n-b^n\) if and only if \(p^{r-1}\mid n\).
Under the conditions, \(v_p(a-b)=1\).
By LTE, \(v_p(a^n-b^n)=v_p(a-b)+v_p(n)=1+v_p(n)\). The divisibility \(p^r\mid a^n-b^n\) is equivalent to \(1+v_p(n)\ge r\), i.e. \(v_p(n)\ge r-1\). This is equivalent to \(p^{r-1}\mid n\).
Prove that for \(m\ge1\), \(v_2(3^{2^m}-1)=m+2\).
Apply the \(p=2\) LTE formula with \(a=3\), \(b=1\), \(n=2^m\).
\(v_2(3^{2^m}-1)=v_2(3-1)+v_2(3+1)+v_2(2^m)-1=1+2+m-1=m+2\).
Ladders