Question

Let n = pq, where p and q are odd primes.

Let the d = gcd(p−1, q−1).

Prove if "bd ≡ 1 mod p", (not bd ≡ 1 mod n)

then n is a pseudoprime for base b.

Answer 1

Answer:

hope u will help

Answer 2

bd ≡ 1 mod p", (not bd ≡ 1 mod n)

Step-by-step explanation:

• By division algorithm, we can find integers q,r with 0 ≤ r < p such that                                        n= pq +r

• therefore, n  ≡ r(Mod p) and consequently,         n^p-1  ≡ r^p-1 (Mod p).         r^p-1 = 1(Mod p)

• here we can observe that r cannot be equal to 0  if r=0,  then n=pq where case (n,p) = p ≠ 1. thus, we have 0<r<p

• now, consider p-1 numbers : 1.r, 2.r, 3.r,....(p-1).r here, none of the numbers is divisible by p. also when these numbers are divided by p. and the reminders are different

hence, bd ≡ 1 mod p where not bd ≡ 1 mod n