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?

  • 0
    Which part confuses you?2011-01-08
  • 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