Show that for all a co-prime to 561. Hint: 561=3 x 17 x 11.

I thought about trying to show (mod 3,17,11), but do not see how this is possible.

Printable View

- May 14th 2013, 09:53 AMPlato13pseudo-prime
Show that for all a co-prime to 561. Hint: 561=3 x 17 x 11.

I thought about trying to show (mod 3,17,11), but do not see how this is possible. - May 14th 2013, 12:23 PMSMADRe: 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, 09:08 PMjohngRe: 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,

3. If p, q and r are primes that divide n, then the product pqr divides n.

So by 1 and 2.

Thus 3, 11 and 17 divide and by 3, the product 3*11*17 = 561 divides - May 15th 2013, 02:40 AMPlato13Re: pseudo-prime
Thank you; very clear solution