Problem E
Pseudoprime numbers
Fermat’s theorem states that for any prime number $p$ and for any integer $a \ge 0$, $a^ p \equiv a \pmod{p}$. That is, if we raise $a$ to the $p$th power and divide by $p$, the remainder is $a$. Some (but not very many) non-prime values of $p$, known as base-$a$ pseudoprimes, have this property for some $a$. (And some, known as Carmichael Numbers, are base-$a$ pseudoprimes for all $a$.)
Given $2 < p \le 1\, 000\, 000\, 000$ and $1 < a < p$, determine whether or not $p$ is a base-$a$ pseudoprime.
Input
Input contains several test cases followed by a line containing “0 0”. Each test case consists of a line containing $p$ and $a$.
Output
For each test case, output “yes” if $p$ is a base-$a$ pseudoprime; otherwise output “no”.
Sample Input 1 | Sample Output 1 |
---|---|
3 2 10 3 341 2 341 3 1105 2 1105 3 0 0 |
no no yes no yes yes |