2
$\begingroup$

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?

  • 1
    Look up primitive roots. and try to find the pattern of their product for small primes.2011-01-08

1 Answers 1

3

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$.

  • 2
    So basically the programming problem seems to be a bogus problem: `printf("1");` :-)2011-01-08