Find all integers $a$ and $b$ such that $$a^3 \equiv b^3 \pmod{7^3}\,,$$ knowing that $7 \nmid ab$.

As a try, I noticed that, since $\gcd(b, 7)=1$, there exists $x \in \mathbb{N}$ such that $b\cdot x \equiv 1 \pmod{7} \Rightarrow b^3 \cdot x^3 \equiv 1 \pmod{7^3}$. Thus $a^3\equiv b^3 \pmod{7^3} \iff (ax)^3\equiv 1\pmod{7^3}$. After this I tried to use Euler's totient function, but I do not know where I should begin.

  • $\begingroup$ you might try to exploit the fact that $a^3 - b^3$ is divisible by $7^3$. $\endgroup$ – enedil Jul 31 '20 at 21:04
  • 1
    $\begingroup$ $18^3\equiv1\bmod7^3$ $\endgroup$ – J. W. Tanner Jul 31 '20 at 21:17
  • $\begingroup$ (a-b)(a2+ab+b2)=0(mod 7^3) then since 7 can’t divide a-b we have 7^3 divides a2+ab+b2. Then I don’t know, perhaps try a2+ab+b2-7^3=0 and solve it as an equation? $\endgroup$ – Charlie Chang Jul 31 '20 at 22:14

Given $7\nmid ab$, $a^3\equiv b^3\bmod 7^3\iff (a/b)^3\equiv1\bmod 7^3$.

Let $x\equiv a/b\bmod 7^3$. We are looking for $x$ such that $7^3|x^3-1=(x-1)(x^2+x+1)$.

Now if $7|x-1$ and $x^2+x+1$, then $7|x^2+x+1-(x+2)(x-1)=3$, a contradiction.

So $7^3|x-1$ (i.e., $x\equiv1\bmod7^3$) or $7^3|x^2+x+1$.

Now we are looking for $x$ such that $x^2+x+1\equiv0\bmod7^3$.

Note that $x\equiv 2$ and $x\equiv 4$ are the solutions to $x^2+x+1\equiv0\bmod7$.

If $x=7k+4$ is a solution to $x^2+x+1\equiv0\bmod7^2$, then $k\equiv2\bmod7$, so $x\equiv18\bmod7^2$.

If $x=7^2k+18$ is a solution to $x^2+x+1\equiv0\bmod7^3$,

then $k\equiv0\bmod7$, so $x\equiv18\bmod7^3$.

If $x=7k+2$ is a solution to $x^2+x+1\equiv0\bmod7^2$, then $k\equiv4\bmod7$, so $x\equiv30\bmod7^2$.

If $x=7^2k+30$ is a solution to $x^2+x+1\equiv0\bmod7^3$,

then $k\equiv6\bmod7$, so $x\equiv324\bmod7^3$.

(I could have argued that, if $x\equiv18$ is a solution,

then $x^4+x^2+1\equiv x+x^2+1\equiv0$, so $x^2\equiv18^2=324$ is a solution too.)

So either $a\equiv b$ or $a\equiv18b$ or $a\equiv324 b\bmod 7^3$, and then $a^3\equiv b^3\bmod 7^3$.


Proposition. For two integers $a$ and $b$, $$a^3\equiv b^3\pmod{7^3}$$ if and only if at least one of the following conditions holds:

  • $a\equiv 0\pmod{7}$ and $b\equiv 0\pmod{7}$,

  • $a\equiv b\pmod{7^3}$,

  • $a\equiv -19b\pmod{7^3}$, and

  • $a\equiv 18b\pmod{7^3}$.

For integers $a$ and $b$, $a^3\equiv b^3\pmod{7^3}$ if and only if $$(a-b)\,(a^2+ab+b^2)\equiv 0\pmod{7^3}\,.$$ If $7\mid a-b$ and $7\mid a^2+ab+b^2$, then it follows that $$3ab=(a^2+ab+b^2)-(a-b)^2\equiv 0\pmod{7}\,,$$ whence $7\mid 3ab$, so $7\mid ab$. This means $7\mid a$ or $7\mid b$. However, as $7\mid a-b$, we conclude that $7\mid a$ and $7\mid b$. Thus, $a^3\equiv 0\equiv b^3\pmod{7^3}$ in this case. From now on, we assume that $7\nmid a-b$ or $7\nmid a^2+ab+b^2$.

In the case $7\nmid a^2+ab+b^2$, we conclude that $7^3\mid a-b$. Therefore, $a\equiv b\pmod{7^3}$, but $7\nmid a$ and $7\nmid b$. The only remaining case is when $7\nmid a-b$.

When $7\nmid a-b$, we get $7^3\mid a^2+ab+b^2$. Thus, $7\mid a^2+ab+b^2$. Now, observe that $$a^2+ab+b^2\equiv (a-2b)(a-4b)\pmod{7}\,.$$ That is, $a\equiv 2b\pmod{7}$ or $a\equiv 4b\pmod{7}$.

Suppose that $a\equiv 2b\pmod{7}$. Then, $a-2b=7k$ for some integer $k$. Therefore, $$a^2+ab+b^2=(2b+7k)^2+(2b+7k)b+b^2=7\left(b^2+5kb+7k^2\right)\,.$$ Because $7^3\mid a^2+ab+b^2$, we deduce that $$7^2\mid b^2+5kb+7k^2\,.$$ Therefore, $$b(b-2k)\equiv b^2+5kb+7k^2\equiv 0\pmod{7}\,.$$ However, we can easily see that $b\not\equiv 0\pmod{7}$. This implies $$b\equiv 2k\pmod{7}\,.$$ Write $b-2k=7l$ for some integer $l$. Then, $$b^2+5kb+7k^2=(2k+7l)^2+5k(2k+7l)+7k^2=7(3k^2+9kl+7l^2)\,.$$ Thus, we need $7\mid 3k^2+9kl+7l^2$. Consequently, $$3k(k+3l)\equiv 3k^2+9kl+7l^2\equiv 0\pmod{7}\,.$$ Because $b-2k=7l$ and $7\nmid b$, we conclude that $7\nmid k$, whence $$k\equiv -3l\pmod{7}\,.$$ Therefore, $k=-3l+7m$ for some integer $m$, whence $$b=2k+7l=(-3l+7m)+7l=l+14m$$ and $$a=2b+7k=2(l+7m)+7(-3l+7m)=-19l+77m\,.$$ Thus, $$a=-19(b-14m)+77m=-19b+343m\equiv -19b\pmod{7^3}\,.$$

Now, suppose that $a\equiv 4b\pmod{7}$. Then, $a-4b=7k$ for some integer $k$. Therefore, $$a^2+ab+b^2=7(3b^2+9kb+7k^2)\,.$$ Again, we can see that $$3b(b+3k)\equiv 3b^2+8kb+7k^2\equiv 0\pmod{7}\,.$$ Ergo, $b\equiv -3k\pmod{7}$. Let $b=-3k+7l$ for some integer $l$. Then, $$3b^2+9kb+7k^2=7(k^2-9kl+21l^2)\,,$$ whence $$k(k-2l)\equiv k^2-9kl+21l^2\pmod{7}\,.$$ Thus, $k\equiv 2l\pmod{7}$. Write $k=2l+7m$. Therefore, $$b=-3k+7l=l-21m$$ and $$a=4b+7k=4(l-21m)+7(2l+7m)=18l-35m\,.$$ Finally, we may write $$a=18(b+21m)-35m=18b+343m\equiv 18b\pmod{7^3}\,.$$

Remark. In principle, there should be a more concise solution using Eisenstein integers. I just opted for an elementary solution.

  • $\begingroup$ Is it valid to say simply that, since OP granted $7\nmid ab$, $a^3\equiv b^3\bmod 7^3\iff (a/b)^3\equiv1\bmod7^3$, and that means $a/b\equiv1\bmod7^3$ or $(a/b)^2+(a/b)+1\equiv0\bmod7^3$, and that last equation can be solved by solving $\bmod 7$ and lifting? $\endgroup$ – J. W. Tanner Jul 31 '20 at 21:55
  • $\begingroup$ @J.W.Tanner Yes, I had that in mind, but since the explanation of the "lifting" would go very much the same way as what I did, so I decided to do what I did, and not did what I could have done. Do you understand what I just wrote? $\endgroup$ – Batominovski Jul 31 '20 at 22:00
  • $\begingroup$ Thank you. I hope you don't mind if I post an alternative answer where I do what you could have done ;-) $\endgroup$ – J. W. Tanner Jul 31 '20 at 22:09
  • 1
    $\begingroup$ @J.W.Tanner I welcome different answers. No worries. $\endgroup$ – Batominovski Jul 31 '20 at 22:10

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.