Kvant Math Problem 241
The exponent $1974$ is large, so direct computation is impossible.
Verified: no
Verdicts: SKIP + SKIP
Solve time: 1m57s
Source on kvant.digital
Problem
Prove that $3^{1974}+5^{1974}$ is divisible by 13.
S. I. Meyzus
Exploration
The exponent $1974$ is large, so direct computation is impossible. Since the statement concerns divisibility by $13$, the natural step is to work modulo $13$.
Compute small powers. Since
$$3^3=27\equiv 1 \pmod{13},$$
the powers of $3$ repeat with period $3$. Also
$$5^2=25\equiv -1 \pmod{13},$$
hence
$$5^4\equiv 1 \pmod{13},$$
so the powers of $5$ repeat with period dividing $4$.
Because
$$1974=3\cdot 658,$$
we obtain
$$3^{1974}=(3^3)^{658}.$$
For the other term,
$$1974=4\cdot 493+2,$$
so
$$5^{1974}=(5^4)^{493}5^2.$$
The only place where an error could hide is the reduction of the large exponents. Each congruence must be carried out carefully.
Problem Understanding
We must prove that the integer
$$3^{1974}+5^{1974}$$
is divisible by $13$.
This is a Type B problem, a pure proof.
The core difficulty is reducing the enormous powers modulo $13$ and showing that the resulting residues add to $0$ modulo $13$.
Proof Architecture
The first claim is that $3^3\equiv 1\pmod{13}$; this follows from $3^3=27=2\cdot13+1$.
The second claim is that $3^{1974}\equiv 1\pmod{13}$; this follows because $1974=3\cdot658$.
The third claim is that $5^2\equiv -1\pmod{13}$; this follows from $25=26-1$.
The fourth claim is that $5^{1974}\equiv -1\pmod{13}$; this follows from $1974=4\cdot493+2$ and $(5^2)^2\equiv1\pmod{13}$.
The final step is to add the two congruences and obtain residue $0$ modulo $13$.
The step most likely to fail under scrutiny is the reduction of $5^{1974}$, since it requires handling both the period and the remainder correctly.
Solution
Since
$$3^3=27\equiv1\pmod{13},$$
and
$$1974=3\cdot658,$$
we have
$$3^{1974}=(3^3)^{658}\equiv1^{658}\equiv1\pmod{13}.$$
Next,
$$5^2=25\equiv-1\pmod{13}.$$
Squaring gives
$$5^4\equiv(-1)^2\equiv1\pmod{13}.$$
Since
$$1974=4\cdot493+2,$$
it follows that
$$5^{1974} =(5^4)^{493}5^2 \equiv1^{493}(-1) \equiv-1 \pmod{13}.$$
Adding the two congruences,
$$3^{1974}+5^{1974} \equiv1+(-1) \equiv0 \pmod{13}.$$
Hence $13$ divides $3^{1974}+5^{1974}$.
This completes the proof.
∎
Verification of Key Steps
The reduction of $3^{1974}$ uses only the identity $1974=3\cdot658$. Since
$$3^3\equiv1\pmod{13},$$
raising both sides to the $658$th power yields
$$3^{1974}\equiv1.$$
A careless argument could incorrectly assume a different period for powers of $3$, but this computation does not require knowing the exact period.
For the second reduction,
$$5^2\equiv-1\pmod{13},$$
so
$$5^4\equiv1\pmod{13}.$$
Using
$$1974=4\cdot493+2,$$
the exponent leaves remainder $2$ upon division by $4$. Forgetting this remainder would give $5^{1974}\equiv1$, which is incorrect. Keeping the remainder produces
$$5^{1974}\equiv5^2\equiv-1.$$
The final addition is
$$1+(-1)=0,$$
which is exactly the residue required for divisibility by $13$.
Alternative Approaches
A different proof uses Fermat's little theorem. Since $13$ is prime and neither $3$ nor $5$ is divisible by $13$,
$$3^{12}\equiv1\pmod{13}, \qquad 5^{12}\equiv1\pmod{13}.$$
Because
$$1974=12\cdot164+6,$$
we obtain
$$3^{1974}\equiv3^6,\qquad 5^{1974}\equiv5^6 \pmod{13}.$$
Now
$$3^3\equiv1\pmod{13},$$
so
$$3^6\equiv1,$$
and
$$5^2\equiv-1\pmod{13},$$
so
$$5^6=(5^2)^3\equiv(-1)^3=-1.$$
Their sum is $0$ modulo $13$.
The main approach is preferable because it uses the shorter periods $3$ and $4$ directly and reaches the result with fewer computations.