1
$\begingroup$

I am seeking the solution to the congruence

$$ 29x^{33} \equiv 27\ \text{(mod 11)} $$

Primitive root is 2 and $ord_{11} (2) =10$. Then I got

enter image description here

so the equation can be field:

$$ lnd_2(29) + 33 lnd_2(x) \equiv lnd2(27)\ \text{(mod 10)} $$

Since $$lnd_a(rs) \equiv lnd_ar + lnd_as \ \text{(mod p-1)}$$

However, how to get a prime number 29 to be the product of two numbers??

$\endgroup$
8
  • 2
    $\begingroup$ $29\equiv 7 \bmod 11$. $\endgroup$
    – lhf
    May 20, 2014 at 11:11
  • $\begingroup$ Oh I see, thank you very much! $\endgroup$
    – Yang Xia
    May 20, 2014 at 11:15
  • $\begingroup$ @YangXia: Have you been able to solve it? $\endgroup$
    – user88595
    May 20, 2014 at 11:18
  • $\begingroup$ @user88595, one more question is, can I make that 33 in the equation into least residue? $\endgroup$
    – Yang Xia
    May 20, 2014 at 11:19
  • 1
    $\begingroup$ @YangXia, no! But you can simplify $33 \bmod 10$. $\endgroup$
    – lhf
    May 20, 2014 at 11:26

2 Answers 2

Reset to default
2
$\begingroup$

Index tables are unneeded since it is $\rm\color{#c00}{easy}$ to take $\,n$'th roots when $\,n\,$ is coprime to $\,p\!-\!1,\,$ e.g.

${\rm mod}\ 11\!:\ 29x^{33}\!\equiv 27\overset{\large\, x^{10}\,\equiv\, 1}\iff\!-4x^3\!\equiv 16\!\!\iff\! x^3\!\equiv -4\!\!\!\overset{\rm\color{#c00}{cube}}\iff\!\! \dfrac{1}x\equiv 2\!\iff\! x \equiv \dfrac{1}2 \equiv \dfrac{12}2 = 6$

$\endgroup$
1
$\begingroup$

First reduce $\bmod 11$: $$ 29x^{33} \equiv 27 \bmod 11 \quad\text{iff}\quad 7x^{33} \equiv 5\bmod 11 $$

Using index calculus gives us $$ ind(7)+33ind(x)\equiv ind(5) \bmod 10 $$ $$ 7+3ind(x)\equiv 4 \bmod 10 $$ $$ 3ind(x)\equiv -3 \bmod 10 $$ $$ ind(x)\equiv -1 \bmod 10 $$ so $ ind(x)=9 $ and $x\equiv 6 \bmod 11$.

$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .