1
$\begingroup$

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?

$\endgroup$
2
$\begingroup$

$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$.

$\endgroup$
  • $\begingroup$ One value of n is 1, but are there any others? $\endgroup$ – Jason Chen May 9 '14 at 4:36
  • $\begingroup$ $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. $\endgroup$ – Daniel Fischer May 9 '14 at 9:15
2
$\begingroup$

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}$

$\endgroup$
  • 1
    $\begingroup$ +1, That can be really helpful in all similar questions :) $\endgroup$ – CODE Jun 22 '14 at 17:50
  • $\begingroup$ See this answer for a closely related viewpoint. $\endgroup$ – Bill Dubuque Aug 26 '14 at 18:26
  • $\begingroup$ See also this answer. $\endgroup$ – Bill Dubuque Mar 28 '15 at 2:56

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.