You are Here: Home >< Maths

# Show that 2 is a primitve root modulo 107 Watch

"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
2. (Original post by Nazzy_HCrest)

"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.

The set of integers 1 to 106 which are coprime to 107 forms a multiplicative group mod 107. The order of this group is

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.
3. Yes there is a shortcut.
You only need to check that
(where q is prime factor- see below) is not congruent to .

Now, in you case, so and .

So check: and are not congruent to 1 (modulo 107).

TSR Support Team

We have a brilliant team of more than 60 Support Team members looking after discussions on The Student Room, helping to make it a fun, safe and useful place to hang out.

This forum is supported by:
Updated: May 18, 2016
Today on TSR

### Does race play a role in Oxbridge admissions?

Or does it play no part?

### The worst opinion about food you'll ever hear

Discussions on TSR

• Latest
• ## See more of what you like on The Student Room

You can personalise what you see on TSR. Tell us a little about yourself to get started.

• Poll
Useful resources

### Maths Forum posting guidelines

Not sure where to post? Read the updated guidelines here

### How to use LaTex

Writing equations the easy way

### Study habits of A* students

Top tips from students who have already aced their exams

## Groups associated with this forum:

View associated groups
Discussions on TSR

• Latest
• ## See more of what you like on The Student Room

You can personalise what you see on TSR. Tell us a little about yourself to get started.

• The Student Room, Get Revising and Marked by Teachers are trading names of The Student Room Group Ltd.

Register Number: 04666380 (England and Wales), VAT No. 806 8067 22 Registered Office: International House, Queens Road, Brighton, BN1 3XE

Reputation gems: You get these gems as you gain rep from other members for making good contributions and giving helpful advice.