0
$\begingroup$

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.

$\endgroup$
  • 4
    $\begingroup$ 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}$. $\endgroup$ – user647486 Apr 19 at 14:44
  • $\begingroup$ @thanks for the edit! $\endgroup$ – user3918597 Apr 19 at 14:45
  • 1
    $\begingroup$ 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$. $\endgroup$ – user647486 Apr 19 at 14:56
  • $\begingroup$ ok most is clear but just to clarify: you get 7 from Euler's totient theorem? $\endgroup$ – user3918597 Apr 19 at 14:56
  • 1
    $\begingroup$ 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$. $\endgroup$ – Robert Israel Apr 19 at 15:59
1
$\begingroup$

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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.