# How to solve $7^x -5x^3 \equiv 0 \quad \pmod{11}?$

I have to study the solvability of the equation $$7^x -5x^3 \equiv 0 \quad \pmod{33}$$ and determine its integer solutions $$x$$ with $$0 \le x \le 110$$.

I started dividing this equation into two equations $$\cases {7^x -5x^3 \equiv 0 \quad \pmod{3} \\ 7^x -5x^3 \equiv 0 \quad \pmod{11}}.$$ For the first one I tried to substitute the values $$0,1,2$$ and found that $$2$$ is the only possibile solution.

Then I tried to solve the second one with the method of indices: $$x \cdot\mbox{ind}_{11}(7)-\mbox{ind}_{11}(5)-3\cdot\mbox{ind}_{11}(x) \equiv 0 \pmod{\phi(11)}.$$ I noticed that $$2$$ is a primitive root $$\pmod{11}$$ and computed its powers which lead to $$2^4 \equiv 5 \pmod{11} \\2^7 \equiv 7 \pmod{11}.$$ The equation became $$x \cdot 7 - 4- 3 \cdot \mbox{ind}_{11}(x) \equiv 0 \pmod{\phi(11)} \quad \longrightarrow \quad 7 x - 3 \cdot \mbox{ind}_{11}(x) \equiv 4 \quad \pmod{\phi(11)}.$$

Then I stopped because I had no clues on how to continue. Have you any ideas?

• $7^x-5x^3\equiv 0$ (mod $3$) would be equivalent to $1^x-2x^3\equiv 0$ (mod $3$) or just $2x^3\equiv 1$ (mod $3$) if that helps. – lurker Jun 13 at 13:24

Instead of using the primitive root $$2$$, note that $$7$$ is a primitive root mod 11, because $$7^2\equiv 5$$ and $$7^5\equiv -1$$. So using 7-indices is a sensible move. We list the values: $$\begin{array}{c|c|c} \hline x\pmod{11} & 5x^3\equiv 7^x\pmod{11} & x\pmod{10} \\\hline 1 & 5&2\\ 2 & 7&1\\ 3 & 3&4\\ 4 & 1&0\\ 5 & 9&8\\ 6 & 2&3\\ 7 &10&5\\ 8 & 8&9\\ 9 & 4&6\\ 10& 6&7\\\hline \end{array}$$ So combining the outer columns, you know ten solutions $$x\pmod{110}$$ and you know $$x\equiv 2\pmod{3}$$. Hence you can write down the ten solutions mod 330, and determine the solutions between 0 and 110.

• Actually there are $10$ solutions mod $110$. – paw88789 Jun 13 at 14:12
• @paw88789 which is why there are 10 solutions mod 330 – user10354138 Jun 13 at 14:12
• I am having trouble making sense of the second and third column headings in your table. I guess the second column is just $5x^3 \pmod{11}$. – paw88789 Jun 13 at 14:14
• @paw88789 but we are solving $5x^3\equiv 7^x$. Now we use the primitive $7$-indices to make the third column – user10354138 Jun 13 at 14:14
• Ten solutions mod 110 should scale up to thirty solutions mod 330. – paw88789 Jun 13 at 14:15

Numerically in pari-gp:

? for(x=0,110,a=Mod(7,33)^x;b=Mod(5*x^3,33);if(a-b==0,print1(x", ")))
14, 38, 83, 86, 95, 101,


Theorycally by using multiplicative order, discrete logarithm and chinese remainder theorem:

? znorder(Mod(7,33))
%1 = 10
?
? for(r=0,32,z=znlog(r,Mod(7,33),10);print(r"    "z))
0    []
1    0
2    []
3    []
4    6
5    []
6    []
7    1
8    []
9    []
10    5
11    []
12    []
13    3
14    []
15    []
16    2
17    []
18    []
19    9
20    []
21    []
22    []
23    []
24    []
25    4
26    []
27    []
28    7
29    []
30    []
31    8
32    []
?
? R=A=[];for(r=0,32,z=znlog(r,Mod(7,33),10);if(#z,R=concat(R,r);A=concat(A,Mod(z,10))))
? R
%4 = [4, 7, 10, 13, 16, 19, 25, 28, 31]
? A
%5 = [Mod(6, 10), Mod(1, 10), Mod(5, 10), Mod(3, 10), Mod(2, 10), Mod(9, 10), Mod(4, 10), Mod(7, 10), Mod(8, 10)]
?
? B3=[];for(i=1,#R,r=R[i];w=polrootsmod(5*x^3-r,3)[1];B3=concat(B3,w))
? B3
%7 = [Mod(2, 3), Mod(2, 3), Mod(2, 3), Mod(2, 3), Mod(2, 3), Mod(2, 3), Mod(2, 3), Mod(2, 3), Mod(2, 3)]
?
? B11=[];for(i=1,#R,r=R[i];w=polrootsmod(5*x^3-r,11)[1];B11=concat(B11,w))
? B11
%9 = [Mod(9, 11), Mod(2, 11), Mod(7, 11), Mod(6, 11), Mod(1, 11), Mod(8, 11), Mod(3, 11), Mod(10, 11), Mod(5, 11)]
?
? B=chinese(B3,B11)
%10 = [Mod(20, 33), Mod(2, 33), Mod(29, 33), Mod(17, 33), Mod(23, 33), Mod(8, 33), Mod(14, 33), Mod(32, 33), Mod(5, 33)]
?
? X=chinese(A,B)
%11 = [Mod(86, 330), Mod(101, 330), Mod(95, 330), Mod(83, 330), Mod(122, 330), Mod(239, 330), Mod(14, 330), Mod(197, 330), Mod(38, 330)]
?
? S=Set();for(i=1,#X,x=lift(X[i]);if(x<=110,S=setunion(S,[x])))
? S
%15 = [14, 38, 83, 86, 95, 101]