Find all positive integers $ n$ such that $ 20^n - 13^n - 7^n$ is divisible by $ 309$.
Problem
Source: Argentina TST 2009
Tags: number theory unsolved, number theory
15.05.2009 22:10
uglysolutions wrote: Find all positive integers $ n$ such that $ 20^n - 13^n - 7^n$ is divisible by $ 309$. Taking mod $ 3$ then $ f(n)=20^n - 13^n - 7^n \equiv (-1)^n-1^n-1^n \equiv (-1)^n-2 (3)$ then $ 3| 20^n - 13^n - 7^n \iff n \equiv 1 (2)$. $ 20^{6k} \equiv 23^k(103)$, $ 13^{6k} \equiv 23^k(103)$, $ 7^{6k} \equiv 23^k(103)$ Taking mod $ 103$ for all the odd remainder mod $ 6$ 1) $ n=1+6k$ $ f(n)\equiv 20 \cdot 23^k- 13 \cdot 23^k-7 \cdot 23^k \equiv 0(103)$ 2) $ n=3+6k$ $ f(n)\equiv 69 \cdot 23^k- 38 \cdot 23^k-38 \cdot 23^k \equiv 23^k (103)$ No solution 3) $ n=5+6k$ $ f(n)\equiv 99 \cdot 23^k- 81 \cdot 23^k-18 \cdot 23^k \equiv 0 (103)$ Then solution is $ \boxed{n=1+6k \ or \ n=5+6k}$
06.11.2011 07:54
lemma.the order of $7$ modulo $103$ is $51$. easy to prove by calculations and I'll just ignore it. proof. mod $3$ it's easy to find that $n$ is $odd$.then let $n=2k+1$.then $20^n-13^n-7^n\equiv (13^k-7^k)(7^{k+1}-13^{k+1})(mod 103)$ hence $103|13^k-7^k$ or$103|13^{k+1}-7^{k+1}$ if $103|13^k-7^k$ then $103|7^{18k}-7^k$ so $7^{17k}\equiv 1(mod 103)$ by lemma,$51|17k$ hence $3|k$. analagously,$3|k+1$ also satisfies the condition. hence $k\equiv 0 or 2(mod 3)$,obtaining $n\equiv 1 or 5(mod 6)$. QED
06.11.2011 07:55
sometimes,the properties of order and original roots are of great use in such number theory problems.