The Student Room Group

Show that 2 is a primitve root modulo 107

Can someone guide me on answering this question please?

"Show that 2 is a primitive root modulo 107" ?

Is there an alternative way than computing all 106 powers of 2 which will take forever!

Any help is much appreciated! Thanks
Original post by Nazzy_HCrest
Can someone guide me on answering this question please?

"Show that 2 is a primitive root modulo 107" ?

Is there an alternative way than computing all 106 powers of 2 which will take forever!

Any help is much appreciated! Thanks


Number theory is definitely not my forté, so take this with a pinch of salt.

From a quick google.

The set of integers 1 to 106 which are coprime to 107 forms a multiplicative group mod 107. The order of this group is ϕ(107)=106\phi(107) = 106

Since the order of an element must divide the order of the group, and 106 = 2x53, it is sufficient to check 1,2,53 as possible orders. If it isn't one of these, then it must be 106, and we have a primative root.
(edited 7 years ago)
Yes there is a shortcut.
You only need to check that
2p1q2^{\frac{p-1}{q}} (where q is prime factor- see below) is not congruent to 11.

Now, in you case, p=107p=107 so p1=106 p-1=106 and 106=253106=2*53.

So check: 21062=2532^{\frac{106}{2}}=2^{53} and 210653=222^{\frac{106}{53}}=2^2 are not congruent to 1 (modulo 107).
(edited 7 years ago)

Quick Reply

Latest