1
$\begingroup$

Finding all no-congruent primitive roots $\pmod{29}$.

I have found that $2$ is a primitve root $\pmod{29}$ Then I found that is it 12 no-congruent roots, since $\varphi(\varphi(29)) = 12$ Then I found that:

$r_1=2^1=2\bmod (29)\\r_2=2^3=8\bmod (29)\\r_3=2^5=3\bmod (29)\\r_4=2^{11}=18\bmod (29)\\r_ 5=2^{13}=18\bmod (29)\\r_6=2^{17}=21\bmod (29)\\r_7=2^{19}=21\bmod (29)\\r_8=2^{23}=10\bmod (29)\\r_9=2^{27}=15\bmod (29)\\r_{10}=2^{29}=2\bmod (29)$

Is $10$ of these roots $12$ roots. Took the power of the primes from $1-29$ (not the primefactors of $\varphi,\ 2$ and $7$), but I am missing $2$ roots, and I don't understand how to find them. I have used all prime powers.

$\endgroup$
  • 1
    $\begingroup$ Why are you sticking to prime exponents? $\gcd(9,28)=1$ so $2^9$ is a primitive root, for instance. Note: it's just an accident of small numbers that most of the numbers in $\{1,2,\cdots, 28\}$ which are prime to $28$ happen to be prime. $\endgroup$ – lulu May 19 at 18:04
  • 1
    $\begingroup$ Thank you, was sticking to prime, but relative primes gives much more sense :) @lulu $\endgroup$ – magnus May 19 at 18:18
2
$\begingroup$

You should use all powers of $2$ that are relatively prime to $28$.

The two roots you are missing are $2^9$ and $2^{15}.$

$9$ and $15$ are not prime (they are multiples of $3$), but they share no factors with $28$.


(I also note that you have wrong values for $2^{13}$ and $2^{19}\bmod29$;

they aren't the same as $2^{11}$ and $2^{17}$, respectively.)


Also, you are missing $2^{25}$; you have $2^{29}$, which is the same as $2^{1}\bmod28$, instead.

| cite | improve this answer | |
$\endgroup$
  • 1
    $\begingroup$ Great user :-). Hi. $\endgroup$ – Sebastiano May 19 at 19:54
2
$\begingroup$

Like my answer here Order of elements modulo p,

We can say $2^r$ is a primitive root of $29$ iff $$(r,\phi(29))=1$$

Now $$\phi(\phi(29))=\phi(7)\cdot\phi(4)=?$$

| cite | improve this answer | |
$\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.