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

• Jan 9th 2011, 07:39 AM
stevanity
abstract algebra [primitive root mod n, euler theorem, fermat theorem]
Try this qn

Quote:

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??
• Jan 9th 2011, 07:52 AM
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.
• Jan 9th 2011, 08:15 AM
stevanity
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 ??
• Jan 10th 2011, 01:10 AM
Swlabr
Quote:

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.

$f(n, p)$ is a function which returns 1 if and only if $n$ is a generator of the multiplicative group of the field, $U_p$.

This result actually holds in general. That is, $\displaystyle\prod_{f(n, p) = 1, 0 for all $p$. 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 $\{1, 2, \ldots, p-1\}$ by $U_p$. Writing $S = \{a: = U_p\}$ then you have two things to prove:

1. If $a \in S$ then $a^{-1} \in S$,
2. If $a \in S$ then $a^{-1} \neq a$ for $p>2$.

Can you see why proving these two things solves the problem?
• Jan 10th 2011, 09:51 AM
Chris L T521
Closing all threads by this user, since its suspected that he's cheated on an official programming competition.