Kvant Math Problem 1288
The number is
Verified: no
Verdicts: SKIP + SKIP
Solve time: 5m17s
Source on kvant.digital
Problem
Prove that the number $235^2+972^2$ is composite.
Leningrad, 1968–1971.
Exploration
The number is
$$235^2+972^2.$$
A direct computation gives
$$235^2=55225,\qquad 972^2=944784,$$
hence
$$235^2+972^2=1000009.$$
The value is close to one million, but factoring $1000009$ directly is not attractive.
A better idea is to look for a common divisor before expanding. Since
$$235=5\cdot 47,\qquad 972=2^2\cdot 3^5,$$
the two numbers are relatively prime, so a common factor of $235$ and $972$ is impossible. For a sum of two squares, congruences are often useful.
Modulo $17$,
$$235\equiv 14\equiv -3,$$
so
$$235^2\equiv (-3)^2=9.$$
Also,
$$972\equiv 3,$$
so
$$972^2\equiv 3^2=9.$$
Therefore
$$235^2+972^2\equiv 9+9=18\equiv 1 \pmod{17},$$
which does not help.
Trying modulo $73$,
$$972=73\cdot 13+23,$$
hence $972\equiv 23\pmod{73}$, while
$$235=73\cdot 3+16,$$
so $235\equiv 16\pmod{73}$. Then
$$16^2+23^2=256+529=785=73\cdot 10+55,$$
again not divisible by $73$.
Since the number is suspiciously close to $1000^2$, rewrite:
$$972=1000-28.$$
Then
$$235^2+972^2 =235^2+(1000-28)^2 =1000000-56000+784+55225 =1000009.$$
Now test divisibility by small primes. The digit sum is $10$, so not divisible by $3$ or $9$. It is odd and does not end in $5$. Modulo $7$,
$$1000009=10^6+9\equiv 1+2\equiv 3.$$
Not divisible by $7$.
Observe instead that
$$1000009=1001^2-1992.$$
This is not useful. A more systematic search suggests checking $293$, because
$$1000009=293\cdot 3413.$$
To discover this factor without knowing it in advance, notice that
$$235^2+972^2=(235+972i)(235-972i).$$
In the ring of Gaussian integers, the prime
$$293=17^2+2^2$$
splits:
$$293=(17+2i)(17-2i).$$
Compute
$$235+972i=(17+2i)(25+54i),$$
since
$$(17+2i)(25+54i)=425-108+(918+50)i=317+968i,$$
which is incorrect. So this route needs adjustment.
Try divisibility directly:
$$235^2+972^2\equiv 0\pmod{293}$$
if
$$972^2\equiv -235^2.$$
Since
$$235\equiv -58,\qquad 972\equiv 93\pmod{293},$$
we get
$$58^2=3364\equiv 141,$$
and
$$93^2=8649\equiv 152.$$
Because
$$141+152=293,$$
their sum is $0$ modulo $293$. This yields a nontrivial divisor.
The potentially dangerous step is the modular arithmetic modulo $293$.
Problem Understanding
We must prove that the integer
$$235^2+972^2$$
is not prime.
This is a Type B problem. The task is to prove the given statement.
The core difficulty is finding a nontrivial divisor of a large-looking number without fully factoring it.
Proof Architecture
First show that modulo $293$, the residues of $235^2$ and $972^2$ add to $0$.
Compute $235\equiv -58\pmod{293}$ and $972\equiv 93\pmod{293}$, then reduce the corresponding squares.
Show that $58^2\equiv141\pmod{293}$ and $93^2\equiv152\pmod{293}$.
Observe that $141+152=293$, hence $235^2+972^2\equiv0\pmod{293}$.
Verify that $235^2+972^2>293$, so divisibility by $293$ gives a proper factorization and the number is composite.
The most delicate point is the reduction of the squares modulo $293$.
Solution
Consider the number
$$N=235^2+972^2.$$
We shall prove that $293$ divides $N$.
Since
$$235=293-58,$$
we have
$$235\equiv -58 \pmod{293}.$$
Therefore
$$235^2\equiv 58^2=3364 \pmod{293}.$$
Because
$$3364=293\cdot11+141,$$
it follows that
$$235^2\equiv141\pmod{293}.$$
Also,
$$972=293\cdot3+93,$$
hence
$$972\equiv93\pmod{293}.$$
Therefore
$$972^2\equiv93^2=8649\pmod{293}.$$
Since
$$8649=293\cdot29+152,$$
we obtain
$$972^2\equiv152\pmod{293}.$$
Adding the two congruences gives
$$N\equiv141+152=293\equiv0\pmod{293}.$$
Thus
$$293\mid N.$$
Since
$$N=235^2+972^2>293,$$
the divisor $293$ is neither $1$ nor $N$. Hence $N$ has a nontrivial divisor and is composite.
This completes the proof.
∎
Verification of Key Steps
The first delicate computation is
$$58^2=3364.$$
Dividing by $293$,
$$293\cdot11=3223,$$
and
$$3364-3223=141.$$
Thus
$$58^2\equiv141\pmod{293}.$$
The second delicate computation is
$$93^2=8649.$$
Since
$$293\cdot29=8497,$$
we obtain
$$8649-8497=152,$$
hence
$$93^2\equiv152\pmod{293}.$$
Finally,
$$141+152=293,$$
so the sum of the residues is exactly one multiple of $293$, yielding
$$235^2+972^2\equiv0\pmod{293}.$$
A careless arithmetic error in either remainder would destroy the divisibility claim.
Alternative Approaches
One may first compute
$$235^2+972^2=1000009.$$
Then a search for factors reveals
$$1000009=293\cdot3413.$$
This proves compositeness immediately, but it obscures how the factor $293$ is found.
The modular approach is preferable because it exhibits a divisor directly from the original expression. Instead of factoring a seven-digit integer, it reduces the problem to two short congruence calculations modulo $293$.