what primes divide $ 1963^{1965}-1963 $

Question

The task is following..

which of the prime numbers $$ 2,3,5,7,11,13,109,151,491 $$

divide $$ z:= 1963^{1965}-1963 $$

Do you have a trick solving this task "quick"?

This is actually a task from a school competition in 1965.

Answer 1

$1963 = 13*151$

$1963-1 = 1962 = 2*3^2*109$

$1963+1 = 1964 = 2^2*491$.

$1963^{1965} - 1963 = 1963(1963^{1964} -1)=1963(1963-1)(1963+1)(1963^2 + 1)(1963^{1960} + 1963^{1956} + .... + 1963 + 1)$.

So of the choices $2,3,5,7,11,13,109,151,491$ we have $2,3,13,109,151,491$ taken care of. That leaves $5,7,11$ to check.

Use Fermat's Little theorem.

$1963^4\equiv 1 \pmod 5$ so $1963^{1964}\equiv 1\pmod 5$ so $5$ divides $1963^{1964} -1$.

... Alternatively.... $1963^2 + 1 \equiv 3^2 + 1 \equiv 10 \equiv 0\pmod 5$. So $5|1963^2 + 1$ and so $5|1963^4 -1$ and $5|1963^{1964}-1$.

$1963^6 \equiv 1 \pmod 7$ so $1963^{1964}\equiv 1963^{2}\equiv 3^2 \equiv 9 \pmod 7$ so $7$ doesnt divide $1963^{1964} -1$ and as $7\not \mid 11963$ we have $7$ doesn't divide $1963^{1965}-1963$.

$1963^{10}\equiv 1 \pmod 11$ so $1963^{1964}\equiv 1963^4 \equiv 5^4\equiv 25^2 \equiv 4^2 \equiv 16 \equiv 5$ so $11$ doesn't divide $1963^{1964}-1$ nor $1963^{1965}-1963$

Answer 2

Fermat's Little Theorem says:

$a^{p-1} \equiv 1\pmod p$

Find $1963\pmod p$ and $1965\pmod {p-1}$

$1963^{1965}\equiv 1\pmod 2\\ 1963^{1965}\equiv 1\pmod 3\\ 1963^{1965}\equiv 3\pmod 5\\ 1963^{1965}\equiv 3^3\pmod 7$

etc.

Answer 3

Take $1963$ common, you'll get

$1963(1963^{1964}-1^{1964})$.

Now continuously break to

$1963(1963^{982}+1)(1963^{491}+1)(1963^{491}-1)$.

$1963$ had factors $13, 151$. Also see that unit digit of $(1963^{982}+1)$ is $0$, therefore $2,5$ are also the factors of $z$. Solve further to get other roots

Answer 4

Obviously $z$ inherits all prime factors of $1962=2\times 3^2\times 109$ and $1963=13\times 151$, and the prime factorization $1964=2^2\times491$ also verifies $491$.

Next we'll use Fermat's last theorem. Modulo $5$, $1963=-2$ and $(-2)^{1965}=(-2)^1$ (because $4|1965-1$), so $5|z$. Modulo $7$, $1963=3$ and $3^{1965}=3^3=-1\ne3$, so $7$ fails. Modulo $11$, $1963=5$ and $5^{1965}=5^5=3125=1\ne5$, so $11$ fails.

Answer 5

$1963=4\times491-1\equiv-1\bmod 491$, so $1963^{1965}-1963\equiv0\bmod 491$

$1963=13\times151\equiv0\bmod151$ and $13$, so $1963^{1965}-1963\equiv0\bmod 151$ and $13$

$1963=18\times109+1\equiv1\bmod109$ and $3$ and $2$, so $1963^{1965}-1963\equiv0\bmod 109$ and $3$ and $2$

By Fermat's little theorem, $1963^4\equiv1\pmod5$,

so $1963^{1965}-1963\equiv(1963^4)^{491}1963-1963\equiv0\pmod 5$.

Also by Fermat's little theorem, $1963^6\equiv1 \pmod7, $

so $1963^{1965}-1963\equiv(1963^6)^{280}1963^3-1963\equiv3^3-3=3(3^2-1)\equiv3\not\equiv0\pmod7$,

and $1963^{10}\equiv1\bmod 11,$ so $1963^{1965}-1963\equiv(1963^{10})^{196}1963^5-1963$

$\equiv5^5-5\equiv5(5^2-1)(5^2+1)\equiv5\times2\times4\equiv7\not\equiv0\bmod11$.

Answer 6

Hint $ $ prime $\ p\mid a^n-a = a(a^{n-1}\!-1)\iff p\mid a\,$ or $\,p\mid a^{n-1}-1.\,$ For the latter, by Fermat

$\!\!\bmod p\!:\ a^{\large 4\cdot 491}\! \equiv 1 \equiv a^{\large p-1}\!\! \iff a^{\large (4\cdot 491,\,p-1)}\equiv1\!$ $\iff\! \bbox[5px,border:1px solid #c00]{a^{\large (4,\,p-1)}\equiv 1}\,$ by $\,\underbrace{491\nmid p\!-\!1}_{\textstyle p\le 491}$

So $\,\color{#90f}{p\mid a(a^4\!-\!1)}=\color{#0a0}{(a\!-\!1)a(a\!+\!1)}\color{#c00}{(a^2\!+\!1)}\,$. In the OP $\,a=1963\,$ and the listed primes (except $7,11$) include all $\rm\color{#90f}{such}$ primes $p\le 491$ except for $61.\,$ Indeed very simple hand calculations show that $\,\bar a = 1963\bmod p \equiv \color{#0a0}{0,\pm1}$ for all listed $p$ except $\,5,7,11$ and of those three only $\,5\,$ has $\,\color{#c00}{\bar a^2\equiv -1}$.

Remark $ $ This yields a closed form for the excluded primes: if $P$ is the product of all listed primes then the excluded primes are those in $\,P/(P,\color{#90f}{a^5\!-a}),\,$ which is $\,77 = 7\cdot 11\,$ here, indeed

$\qquad\qquad$