# How to find all solutions for : $a^3 \equiv b^3 \pmod{7^3}$, knowing that $7 \nmid ab$.

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.

• you might try to exploit the fact that $a^3 - b^3$ is divisible by $7^3$. – enedil Jul 31 '20 at 21:04
• $18^3\equiv1\bmod7^3$ – J. W. Tanner Jul 31 '20 at 21:17
• (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? – 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.

• 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? – J. W. Tanner Jul 31 '20 at 21:55
• @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? – Batominovski Jul 31 '20 at 22:00
• Thank you. I hope you don't mind if I post an alternative answer where I do what you could have done ;-) – J. W. Tanner Jul 31 '20 at 22:09
• @J.W.Tanner I welcome different answers. No worries. – Batominovski Jul 31 '20 at 22:10