\section*{Exercise 2 - 041242}

It is to be decided by which of the prime numbers 2, 3, 5, 7, 11, 13, 109, 151, 491 the number \(z = 1963^{1965} - 1963\) is divisible.
}

It holds that:

\[
z=1963^{1965}-1963=1963\left(1963^{1964}-1\right)=1963\left(1963^{982}+1\right)\left(1963^{491}+1\right)\left(1963^{491}-1\right)
\]

Because

\[
a^{k}-1=(a-1)\left(a^{k-1}+a^{k-2}+\ldots+1\right)
\]

for every positive integer \(k\) and every \(a\), and

\[
a^{k}+1=(a+1)\left(a^{k-1}-a^{k-2}+\ldots+1\right)
\]

for every odd natural \(k\) and every \(a\), it follows that:

\[
z=1962 \cdot 1963 \cdot 1964 \cdot P
\]
where \(P\) is the product of the remaining factors. Since

\[
1962=2 \cdot 3^{3} \cdot 109 ; \quad 1963=13 \cdot 151 ; \quad 1964=2^{4} \cdot 491
\]

\(z\) is divisible by \(2,3,13,109,151,491\). It holds that

\[
1963^{1964}-1=\left(1963^{4}\right)^{491}-1
\]

The last digit of \(1963^{4}\) is 1, so the last digit of \(\left(1963^{4}\right)^{491}\) is also 1. Therefore, the last digit of \(1963^{1964}-1\) is 0, which means this number is divisible by 5, and thus \(z\) is also divisible by 5.

Therefore, \(z\) is divisible by all the specified prime numbers.

\section*{Adapted from \([5]\)}