In: Computer Science
Using Fermat't Little Theorem for primality test. Answer the following. Show work for credit.
(a) Test whether each of the following numbers is primes: 101, 341, and 1105. Try at least two bases if needed, and state if the number is pseudoprime to any base you try. You may use a claculator to compute large powers. (MS Excel can be used)
(b) Find a composit number that is pseudoprime to base 3 and 7 but not pseudoprime to base 2
note (MS Excel can be used)
a)Fermat's little theorem states that, Let 'p' be a prime number
and a be a non-negative integer which is relatively prime to
'p',
GCD(a,b)=1 such that,
a^p-1 ≡ 1 (mod p) OR a^p-1%p=1
If a given number is prime, then the method returns true. If the
number is composite, then it may return true or false, but the
probability of resulting incorrect result for a composite is low
and it can be reduced by doing more iterations.
1) let's find 101 is prime or not...
Since 101 is prime, 2^100 ≡ 1 (mod 101)
=2^100 mod 101
=2^10^10 mod 101
=1024^10 mod 101
=14^10 mod 101
=(-6)^5 mod 101
=-216*36 mod 101
=-14*36 mod 101
=-504 mod 101
=505–504
=1
ie,The number 101 is pseudoprime [or 2^101 = 1].
2) let's find 341 is prime or not...
Since 341 is prime, 2^340 ≡ 1 (mod 341) [or 2^341 = 1]
here 341 is prime and 2 and p are coprime then,
The remainder is 1.
ie, The number 341 is pseudoprime
3) let's find 1105 is prime or not...
Since1105 is prime, 2^1104 ≡ 1 (mod 1105)
By Fermat’s Little Theorem,
here, a^p−1 ≡ 1(mod p) if 'a' is relatively prime to 'p'. that
means b is relatively prime to 1105.
so 1105 is a prime number.[or 2^1105 = 1]
b)91 is a pseudoprime to the base 3 but not to the base 2.
n=91=7*13 is a composite number
so 312 ≡ 1(mod 7)
312 ≡ 1(mod 13)
= 3
12 ≡ 1(mod 7 * 13) i.e 312 ≡ 1(mod 91) by result 1.2.1.
Now 391 = (312)
7 * 3
7 ≡ 1
7 * 2187 ≡ 3(mod 91).
ie, 91 is a pseudoprime to the base 3.
Similarly, 212 ≡ 1(mod 91) and 291 = (212)
7 * 2
7 ≡ 1
7 * 128 ≡
37(mod 91)
ie,91 is not a pseudoprime to the base 2
and,
6 is a pseudoprime to the base 7 but not to the base 2.
Hope you got the correct answer...
Please like...Thank you!