Multiples of 1971

Question

Find the smallest positive integer $a$ such that $1971$ divides $50^{n}+a \cdot 23^n$ for all odd integers $n$.

I would re-write under this form $$1971m-50^n=a \cdot 23^n$$ But where to go next?

Answer 1

Our strategy:

Solve the problem for $n=1$ and then show that the solution works also for $n>1$.

First we find the smallest positive integer $a$ such that the divisibility by 1971 holds for $n=1$. This can be done, by finding the smallest $m$ such that $23$ divides $$m\cdot 1971-50\equiv m\cdot 16-4 \pmod{23},$$ which is $m=6$ (I found it by hand), and then $a=(m\cdot 1971-50)/23=512$.

Finally, we show that for such $a$, the divisibility by 1971 holds also for any odd number $n=2k+1$, for $k>0$: $$50^{n}+a \cdot 23^n=50^{2k+1}+512 \cdot 23^{2k+1}=50\cdot (2500)^k +11776\cdot (529)^k \\\equiv 50\cdot (529)^k -50\cdot (529)^k=0 \pmod{1971}.$$

P.S. I tried to wrote a very elementary proof so I did not use CRT.

Answer 2

$1971=3^3\cdot 73$ and $50\equiv 23\pmod{3^3}$, $50\equiv -23\pmod{73}$, hence we must have $$ 23^n (a-1)\equiv 0\pmod{73} $$ $$ 23^n (a+1)\equiv 0\pmod{27} $$ hence $a\equiv 1\pmod{73}$ and $a\equiv -1\pmod{27}$ give, by the CRT, $$ a \equiv \color{red}{512}\pmod{1971}. $$

Answer 3

Hint:

$1971$ and $23$ are coprime, so there are integers $x$ and $y$ so that

$$23x + 1971y = 1$$

i.e. $x$ is the inverse of $23$ modulo $1971$. Therefore

$$50^n + a\cdot 23^n \equiv 0 \pmod{1971} \iff -(50\cdot x)^n \equiv a \pmod{1971}$$

Answer 4

$1971 = 27\cdot 73$. Consider the problem modulo 73: $$ -(-23)^n \equiv a\cdot (23)^n \implies 1 \equiv a \pmod{73} $$ since $n$ is odd. Now consider the problem modulo 27: $$ -(+23)^n \equiv a\cdot (23)^n \implies -1 \equiv a \pmod{27} $$ So we need a number which is congruent to $1$ mod $73$ and $-1$ mod $27$. And to be the smallest positive number, this will have to be a number which is between $1\cdot 27 -1$ and $73\cdot 27 -1$.

Well, there are only $26$ possible choices, and we easily find that this number is $19\cdot 27 -1 = 512$.