# congruence and complex numbers

I am looking at this paper http://ieeexplore.ieee.org/xpl/articleDetails.jsp?arnumber=74138 and am confused by a step.

The problem is to find a minimal solution to $A^4 + B^4 + C^4 = D^4$ in the positive integers. To speed up the problem by filtering out certain D,C as candidates, the author works down to $D^4 - C^4 \equiv 0 \pmod{625}$ which I understand. He then breaks up this difference into 4 complex factors which I understand.

He then states that for $D+iC \equiv 0 (\mod 625)$ to be true, $C \equiv iD \mod 625$ which makes sense. He then states that this requires that $C \equiv 182D \mod 625$ which I don't understand - where is 182 coming from, etc?

I assume this uses some properties of congruence and complex numbers that I don't know and I don't seem able to find the right google terms to learn about it. Can someone please explain how this is done or what terms to search for?

I see below where the 182 is coming from ($182 \equiv -1 \pmod{625}$) but I'm not sure I have the modular algebra correct...

Assume below all are mod 625.

Given:

$C \equiv iD$

square both sides

$C^2 \equiv -1D^2$

$182^2 \equiv -1$

$C^2 \equiv 182^2D^2$

take sqrt of both sides

$C \equiv 182D$

Is the logic above valid?

-

The point is that for all powers $5^k$ of $5$, there exists a number $s_k$ such that $s_k^2\equiv -1\pmod{5^k}$ (and that $s_k\equiv s_{k-1} \pmod{5^{k-1}}$), and then $s_k$ plays the role of $i$ modulo $5^k$.
(Expilictly, $x^2+y^2$ factors as $(x-s_ky)(x+s_ky)$ modulo $5^k$.)
You can verify that $182^2\equiv-1\pmod{625}$ by a calculator.
Or, just start to calculate it by hand: Let $s_1:=2$ (as $2^2\equiv-1\pmod5$). Then we are looking for $s_2=5x+s_1$ with $x\in\Bbb Z/5\Bbb Z$ that makes $s_2^2\equiv -1\pmod{25}$, and so on.
The right question is: 'What does the symbol $i$ mean at all in the congruence $D+iC\equiv 0\pmod{625}$?' And the answer is: $i$ is nothing but a root of $x^2+1$ in $\Bbb Z/625\Bbb Z$. So, now it means $i=182$ (or $i=625-182$ is equally good). – Berci Jan 20 '14 at 0:29