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

elementary-number-theorymodular arithmeticpolynomials

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.

Best 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.

Related Question