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

• Jan 9th 2011, 06: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, 06: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, 07: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, 12: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.

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

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

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

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