Y Practice Set - Prime Numbers

Start

2020-07-17 15:00 AKDT

Y Practice Set - Prime Numbers

End

2020-07-24 13:00 AKDT
The end is near!
Contest is over.
Not yet started.
Contest is starting in -70 days 14:18:56

Time elapsed

166:00:00

Time remaining

0:00:00

Problem A
Pseudoprime numbers

/problems/pseudoprime/file/statement/en/img-0001.jpg

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