Surely there are more numbers than just "2" that are coprime to 35?
Hey everyone, couple problems I am stuck on.
1. Let be an odd prime and . Show
2. is an integer such that , show that
and then deduce there exists no primitive roots modulo 35.
I don't know how to do question 1 so need a lot of help for this one.
For question 2, a must be coprime to 35, so is it good enough to just say and show ?
And how do I do the second part of q2?
Thanks all for your help.
since φ(35) = φ(5)φ(7) = 24, you must show that no integer a such that gcd(a,35) = 1 has multiplicative order 24 (mod 35).
it suffices to check the list of such integers between 1 and 34, namely:
{1,2,3,4,6,8,9,11,12,13,16,17,18,19,22,23,24,26,27 ,29,31,32,33,34}.
you don't have to check every power, just 2,3,4,6,8, and 12 (if none of those powers are congruent to 1, you've found a primitive root).
if you save your calculations, you can save some time, by noticing that:
<2> = {2,4,8,16,32,29,23,11,22,9,18,1}, so none of these have order 24, since they are all powers of 2 (mod 35).
so, for example: 29^12 = (2^5)^12 = (2^12)^5 = 1^5 = 1 (mod 35).
for your first question, do you know wilson's theorem?