Thread: abstract algebra [primitive root mod n, euler theorem, fermat theorem]

Try this qn

For a prime number p the set of co-primes less than or equal to it is given by {1,2,3,4,...p-1} .

We define f(x,p) 0<x<p = 1 if and only if all the numbers from 1 to p-1 can be written as a power of x in modulo-p arithmetic .

Let n be the largest 12-digit prime number . Find the product of all integers j less than n such that f(j,n)=1, in modulo-n arithmetic

n is 999999999989
The answer for this is 1.
How is it??
Please can anyone explain?

Well, it is pretty easy to guess from the answer what happens. You are asked for "the product of all positive integers less than n such that ..." and find that the product is 1. The only way a product of integers can equal 1 is if all the integers are 1! It must be the case that the only positive integer, x, such that "every integer from 1 to p-1 can be written as a power of x in modulo p" is 1 itself.

then the function f(j,n) must be j mod n
This only 1 mod 999999999989 = 1

But how to find out that f(j,n) = j mod n ??

Originally Posted by HallsofIvy

Well, it is pretty easy to guess from the answer what happens. You are asked for "the product of all positive integers less than n such that ..." and find that the product is 1. The only way a product of integers can equal 1 is if all the integers are 1! It must be the case that the only positive integer, x, such that "every integer from 1 to p-1 can be written as a power of x in modulo p" is 1 itself.

This is not true.

is a function which returns 1 if and only if is a generator of the multiplicative group of the field, .

This result actually holds in general. That is, for all . The reason is actually quite elegant...if you know about groups. I am therefore going to assume that you, stevanity, know about groups. If you do not, no probs! I'll write it down a different way.

So, denote by . Writing then you have two things to prove:

1. If then ,
2. If then for .

Can you see why proving these two things solves the problem?

Closing all threads by this user, since its suspected that he's cheated on an official programming competition.

Thread closed.