pseudo-prime

• May 14th 2013, 08:53 AM
Plato13
pseudo-prime
Show that $\displaystyle a^{560}=1 mod(561)$ for all a co-prime to 561. Hint: 561=3 x 17 x 11.

I thought about trying to show $\displaystyle a^{560}=1$ (mod 3,17,11), but do not see how this is possible.
• May 14th 2013, 11:23 AM
Re: pseudo-prime
561 is a Poulet number and is considered a pseudoprime . So you can apply fermat's little theorem on it.
• May 14th 2013, 08:08 PM
johng
Re: pseudo-prime
Hi,
You need just a few elementary facts:
1. If a is co-prime (relatively prime in U.S.) to n and p is any divisor of n, a is relatively prime to p.
2. If a is relatively prime to a prime p, $\displaystyle a^{p-1}\equiv1 (\text{mod}\, p)$
3. If p, q and r are primes that divide n, then the product pqr divides n.

So $\displaystyle (a^2)^{280}\equiv1^{280}(\text{mod}\, 3)\equiv1 (\text{mod}\, 3)$ by 1 and 2.
$\displaystyle (a^{10})^{56}\equiv1^{56}(\text{mod}\, 11)\equiv1 (\text{mod}\, 11)$
$\displaystyle (a^{16})^{35}\equiv1^{35}(\text{mod}\, 17)\equiv1 (\text{mod}\, 17)$

Thus 3, 11 and 17 divide $\displaystyle a^{560}-1$ and by 3, the product 3*11*17 = 561 divides $\displaystyle a^{560}-1$
• May 15th 2013, 01:40 AM
Plato13
Re: pseudo-prime
Thank you; very clear solution