# Divisibility of sum of powers: $\ 323\mid 20^n+16^n-3^n-1\$ for which $n?$

I found this question in my Math Challenge II Number Theory packet: Find all positive integers $n$ that satisfy $323|20^n+16^n-3^n-1$. I don't even have any idea how to approach this question. Any suggestions?

$323 = 17\cdot 19$. So $323$ divides $20^n+16^n-3^n-1$ if and only if both its prime factors, $17$ and $19$, divide it. We have

$$20^n + 16^n - 3^n - 1 \equiv 3^n + (-1)^n - 3^n - 1 \pmod{17}$$

and

$$20^n + 16^n - 3^n - 1 \equiv 1^n + (-3)^n - 3^n - 1 \pmod{19}.$$

From that, it is easy to find the desired $n$.

• One value of n is 1, but are there any others? – Jason Chen May 9 '14 at 4:36
• $n = 1$ doesn't work, $20^1+16^1-3^1-1 = 32$. $n=2$ does work, $20^2+16^2-3^2-1 = 400 + 256 - 9 - 1 = 656 - 10 = 646 = 2\cdot 323$. If you look at the congruences modulo $17$ and modulo $19$, there is something in either case that you can simplify. – Daniel Fischer May 9 '14 at 9:15

With slightly more effort we can prove a much more general result, namely

Theorem $\$ If $\,\ m\mid a\!-\!c,\,\ \overline m \mid a\!-\!d\$ and $\ m,\overline m,b\,$ are pairwise-coprime then

$\qquad\qquad\quad m\overline m\mid e = a^n\!+b^n\!-c^n\!-d^n\iff {\rm lcm}({\rm ord}_m(d/b),{\rm ord}_{\overline m}(c/b))\mid n$

Proof $\$ Note $\,(m,\overline m)= 1\,\Rightarrow\,{\rm lcm}(m,\overline m) = m\overline m,\$ so $\ m\overline m\mid e\iff m,\overline m\mid e$

$\quad {\rm mod}\ m\!:\ a\equiv c\,$ so $\ e\equiv b^n\!-d^n\equiv 0\! \overset{(b,m)=1}\iff\! (d/b)^n\equiv 1\iff {\rm ord}_m(d/b)\mid n$

$\quad {\rm mod}\ \overline m\!:\ a\equiv d\,$ so $\ e\equiv b^n\!-c^n\equiv 0 \!\overset{(b,\overline m)=1}\iff\! (c/b)^n\equiv 1\iff {\rm ord}_{\overline m}(c/b)\mid n$

So $\,m,\overline m\mid e\!\iff\! {\rm ord}_m(d/b)\mid n,\ {\rm ord}_{\overline m}(c/b)\mid n\!\iff\! {\rm lcm}({\rm ord}_m(d/b),{\rm ord}_{\overline m}(c/b))\mid n\ \$ QED

You have $\ \overset{\Large 17\ \mid\ 20-3}{m\mid a\!-\!c},\,$ and $\ \ \overset{\Large 19\ \mid\ 20-1 }{\overline m\mid a\!-\!d }$ and $\overset{\Large 17,\,19,\,16}{\,m,\,\overline m,\,b}\$ are paiwise coprime, and

$\qquad\quad {\rm mod}\ m=17\!:\,\ d/b = 1/16\equiv 1/{-}1\equiv -1\,$ has order $\,\color{#c00}2$

$\qquad\quad {\rm mod}\ \overline m=19\!:\,\ c/b = 3/16\equiv 3/{-}3\equiv -1\,$ has order $\,\color{#0a0}2$

$\begin{eqnarray}\text{By the Theorem}\ \ \ m\overline m&\mid&\ \ a^n &+&\ \ b^n&-&c^n&-&d^n&\iff& {\rm lcm}({\rm ord}_m(d/b),{\rm ord}_{\overline m}(c/b))\mid n\\ \\ {\rm i.e.}\quad 323= 17\cdot 19&\mid& 20^n&+&16^n&-&3^n&-&1^n&\iff& {\rm lcm}(\color{#c00}2,\color{#0a0}2)=2\mid n \end{eqnarray}$

• +1, That can be really helpful in all similar questions :) – CODE Jun 22 '14 at 17:50
• See this answer for a closely related viewpoint. – Bill Dubuque Aug 26 '14 at 18:26