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

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.

• 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. – lulu May 19 at 18:04
• Thank you, was sticking to prime, but relative primes gives much more sense :) @lulu – magnus May 19 at 18:18

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.

• Great user :-). Hi. – Sebastiano May 19 at 19:54

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)=?$$