- #1
kathrynag
- 598
- 0
(1). Prove the following statements.
(a). When n = 2p, where p is an odd prime, then a^(n-1) = a (mod n) for any integer a.
(b). For n = 195 = 3 * 5 *13, we have a^(n-2) = a (mod n) for any integer a
If I am correct Fermat's Theorem comes into play.
a)n=2p
a^(2p-1)
a^(2p)*(1/a)
a^2(a^p)*(1/a)
a^p=a for any prime
a^2*(a)*(1/a)
a^(2-1)*a
a*a
a^2
a mod n
b)a^(195-2)
a^(193)
193 is a prime so by Fermat's Theorem, a^p=a mod p
So a^193=a mod(193)
and thus a^193=a mod (195)
I feel like I did something wrong on both problems...
(a). When n = 2p, where p is an odd prime, then a^(n-1) = a (mod n) for any integer a.
(b). For n = 195 = 3 * 5 *13, we have a^(n-2) = a (mod n) for any integer a
If I am correct Fermat's Theorem comes into play.
a)n=2p
a^(2p-1)
a^(2p)*(1/a)
a^2(a^p)*(1/a)
a^p=a for any prime
a^2*(a)*(1/a)
a^(2-1)*a
a*a
a^2
a mod n
b)a^(195-2)
a^(193)
193 is a prime so by Fermat's Theorem, a^p=a mod p
So a^193=a mod(193)
and thus a^193=a mod (195)
I feel like I did something wrong on both problems...