Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

The problem is:

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

Can anyone give me a better explanation?

share|improve this question
    
Which part confuses you? –  Qiaochu Yuan Jan 8 '11 at 21:57
1  
Look up primitive roots. and try to find the pattern of their product for small primes. –  user17762 Jan 8 '11 at 22:00
add comment

1 Answer

up vote 3 down vote accepted

The numbers $x$ you are looking for are called primitive roots.

It is well known that the product of primitive roots of an odd prime $p \gt 3$ is $1 \mod p$.

For a proof: If $g$ is a primitive root, what can you say about $g^{-1}$?

Note: $g^{-1}$ is the number $\mod p$ such that $g g^{-1} = 1 \mod p$.

share|improve this answer
2  
So basically the programming problem seems to be a bogus problem: printf("1"); :-) –  Aryabhata Jan 8 '11 at 22:36
    
Thank you so much! –  SuprDewd Jan 8 '11 at 22:49
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.