Pseudoprime

what is pseudoprime ?

"A pseudoprime is a composite number that passes a test or sequence of tests that fail for most composite numbers. Unfortunately, some authors drop the "composite" requirement, calling any number that passes the specified tests a pseudoprime even if it is prime. Pomerance, Selfridge, and Wagstaff (1980) restrict their use of "pseudoprime" to odd composite numbers. "Pseudoprime" used without qualification means Fermat pseudoprime. "

So now you know ! :wink:

You need to show that 19^(45-1) = 1 mod 45

Calculate 19^2 mod 45
It's easy from there...

what is composite number ?

A composite number is a positive integer which is not prime.

I knew this part as well...

Please elaborate...

This is what I've tried thus far...

We know that 45 = 5 * 9, hence is composite as you mentioned...

We need to show that 19^45 = 19 (mod 45)

But to establish this it is sufficient to show that:

19^45 = 19 (mod 9) and 19^45 = 19 (mod 5)

since gcd(9,5) = 1 (they are relatively prime)

Also, gcd(19,5) = 1 and this implies that 19^4 = 1 (mod 5) (Fermat)

then what?

I appreciate your definition but I'd appreciate even more if you could say something pertaining to the problem at hand...

We know that 45 = 5 * 9, hence is composite as you mentioned...

We need to show that 19^45 = 19 (mod 45)

But to establish this it is sufficient to show that:

19^45 = 19 (mod 9) and 19^45 = 19 (mod 5)

since gcd(9,5) = 1 (they are relatively prime)

Also, gcd(19,5) = 1 and this implies that 19^4 = 1 (mod 5) (Fermat)

then what?

i still don't understand what pseudoprime is
as i know, prime is a positive integer, larger than 1 ,whose its gcd is itself.
therefore, i guess pseudoprime is a number seem to be prime but actually not. Am I right ?
1 request, what is Fermat theorem about the prime ? I forgot it because it's been a long time since I stopped studying algebra :wink:

Perhaps my method is a bit more brute force than you're looking for, but if
19^2 = 1 mod 45 (it does)
then
(19^2)^22 = 19^44 = 1 mod 45