# Why is $x = 25n + 9$ in the equation: $3=(3388997632 x^{23}) \text{ mod } 25$?

Apparently the general solution of this:

$$3=(3388997632\cdot x^{23}) \text{ mod }25$$

is $$x = 25n + 9$$, where $$n$$ is any natural number, it seems?

I get how there is connection with $$25$$ as modulo, that is: $$x =\text{modulo }n + 9$$ but can't see where 9 comes from despite being multiple of 3. I am also seeking general solution to these type of equations, as above...or with variables in letters:

$$y = (ax^n)\text{ mod }n+2$$

Apparently, sometimes but not always the solution for $$x$$ is just as above: modulo times any number plus some other number? Also it seems that if $$ax^n$$ is negative there is no easy "general solution" in other words the general solution doesn't apply here as outlined above. thanks in advance.

• That big number is $=7\pmod{25}$. By Euler's theorem $x^{20}=x^{\phi(25)}=1\pmod{25}$. That means that your equation is the same as $7x^{3}=3\pmod{25}$. Now, $7*18=1\pmod{25}$, and $3*18=4\pmod{25}$. Therefore, the equation is equivalent to $x^3=4\pmod{25}$. You can easily check that $9^3=4\pmod{25}$. – user647486 Apr 19 at 14:44
• @thanks for the edit! – user3918597 Apr 19 at 14:45
• To deduce that $9$ is the only solution, you can solve first $x^3=4=-1\pmod{5}$, which only requires checking $5$ possible remainders. You get that $x=4\pmod{5}$ is the only solution. Then you search for solutions of this form $5k+4$ of the original equation: $(5k+4)^3=4\pmod{25}$. This reduces to $3\cdot5\cdot4^2k+4^3=4\pmod{25}$, which gives $3\cdot 5\cdot 8\cdot k+5=0\pmod{25}$. This has solution $k=1\pmod{5}$. Therefore, the solutions to the original equation are of the form $5k+4$, with $k=5n+1$. This is, the solutions are of the form $5n+9$. – user647486 Apr 19 at 14:56
• ok most is clear but just to clarify: you get 7 from Euler's totient theorem? – user3918597 Apr 19 at 14:56
• If your slave isn't handy, note that $100 \equiv 0 \bmod 25$, so you just have to look at the last two digits of $3388997632$. – Robert Israel Apr 19 at 15:59

## 1 Answer

Here's how it connects: $$3\equiv(((33889976\cdot4+1)\cdot25+7)\cdot x^{23}) \pmod{ 25}\implies 3\equiv 2\cdot x^3\pmod 5\\\implies-1\equiv x^3\pmod 5\implies x=5y+4$$ Then applying polynomial remainder theorem, Euler and negative versions to simplify a modular arithmetic fraction, to each case ( we know the base is coprime) we'll see: $$4\equiv 9^{3}\pmod{25}$$ which shows the base to be 9 mod 25.