Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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|cite|improve this question
Which part confuses you? – Qiaochu Yuan Jan 8 '11 at 21:57
Look up primitive roots. and try to find the pattern of their product for small primes. – user17762 Jan 8 '11 at 22:00
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|cite|improve this answer
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

Your Answer


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.