solve x for a cubic congruence equation with large prime mod.

Question

For $x^3 = 123456789 \pmod{1000000007}$ given $1000000007$ is a prime. Find $x$.

My school only teach us about linear congruence equation, and it is an extra credit question. Therefore, I think the question can solve by using the concept only in linear congruence equation.

Original, for $ax = b \pmod{k}$, i usually would do an extended euclid algorithm. However, in this case, seem the algorithm cannot be apply.

Can anyone give me some helps??

Answer 1

I can't find an easy way to show this by hand (although it is still possible). However, I am presenting an answer assuming the prime factorization of $z$ is known (or that the use of a calculator is tolerated... for this time) which makes things slightly more tractable. (I'm very new to number theory so perhaps there is a more straightforward way to go about it though...)

Let $p=1000000007, z=123456789$

$z^{p-1}\equiv1\pmod p$ by Fermat's little theorem

So either $z^{\frac{p-1}{2}}\equiv1\pmod p$ or $z^{\frac{p-1}{2}}\equiv-1\pmod p$

$1$ and $-1$ are obviously solutions to the equation $x^2\equiv 1\pmod p$ and there cannot be a third possibility because we are solving a second order equation on a commutative field of integers mod $p$, which means there are at most $2$ roots.

It can be shown that $z^{\frac{p-1}{2}}\equiv1\pmod p$, either by direct computation (very tedious by hand), or by showing it is a quadratic residue using reciprocity laws, assuming the knowledge of the prime factorization of $z$ (still not straightforward). I am going to show the latter, which nonetheless assumes the prime factorization is known (or has been checked... unfortunately, the prime numbers involved are huge for the average human, and I can't think of an easy way without a calculator or knowing the result beforehand).

$123456789=3^2\times3607\times3803$

Using quadratic reciprocity laws:

$z^{\frac{p-1}{2}}\equiv(123456789,1000000007)$

$=(9,1000000007)\times(3607,1000000007)\times(3803,1000000007)$ $=(-1)\times(1000000007,3607)\times(-1)\times(1000000007,3803)$ $=(2541,3607)\times(1157,3803)$ $=(3\times7\times11^2,3607)\times(13\times89,3803)$ $=(3,3607)\times(7,3607)\times(13,3803)\times(89,3803)$ $=(-1)\times(3607,3)\times(-1)\times(3607,7)\times(3803,13)\times(3803,89)$ $=(1,3)\times(2,7)\times(7,13)\times(65,89)$ $=1\times1\times(13,7)\times(5\times13,89)$ $=(6,7)\times(5,89)\times(13,89)$ $=(2\times3,7)\times(89,5)\times(89,13)$ $=1\times(3,7)\times(4,5)\times(11,13)$ $=(-1)\times(7,3)\times(13,11)$ $=(-1)\times(1,3)\times(2,11)$ $=(-1)\times1\times(-1)$

$=1$

(I hope I didn't make mistakes which cancel out)

So, $z^{\frac{p-1}{2}}\equiv1\pmod p$ and $z^{\frac{p+1}{2}}\equiv z\pmod p$

Besides,

$\frac{p+1}{2}\equiv\frac{2+1}{2}\equiv0 \pmod 3$

Therefore,

$x=z^{\frac{(p+1)}{6}}+pk$ are solutions, with $k$ integral.

They are the only solutions because $\gcd(3,p-1)=1$ and thus the map $x\rightarrow x^3$ is injective mod $p$