1
$\begingroup$

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?

Thank you in advance.

$\endgroup$
  • 1
    $\begingroup$ $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. $\endgroup$ – lurker Jun 13 at 13:24
0
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ Actually there are $10$ solutions mod $110$. $\endgroup$ – paw88789 Jun 13 at 14:12
  • $\begingroup$ @paw88789 which is why there are 10 solutions mod 330 $\endgroup$ – user10354138 Jun 13 at 14:12
  • $\begingroup$ 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}$. $\endgroup$ – paw88789 Jun 13 at 14:14
  • $\begingroup$ @paw88789 but we are solving $5x^3\equiv 7^x$. Now we use the primitive $7$-indices to make the third column $\endgroup$ – user10354138 Jun 13 at 14:14
  • $\begingroup$ Ten solutions mod 110 should scale up to thirty solutions mod 330. $\endgroup$ – paw88789 Jun 13 at 14:15
0
$\begingroup$

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]
$\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.