This question concerns primality testing. Recall Fermat's Little Theorem: For any prime p and integer a, a²-1 = 1 mod p. It happens that the converse to FLT is often but not always true. That is, if n is composite and a is an integer, then more often than not an−1‡1_mod n. We can use this as the basis of a simple primality test, called the Fermat Test. For a € Zn we make the following definitions. 1) We call a a Fermat Liar for n if a^−1 = 1_mod n, where a ‡ (0, 1, n − 1). 2) We call a a Fermat Witness for n if an−¹ ‡1_mod n, where a ‡ (0, 1, n − 1). - If a number is composite, then 2 is very often a Fermat Witness. What is the smallest composite integer n greater than 4157 for which 2 is not a Fermat Witness?
This question concerns primality testing. Recall Fermat's Little Theorem: For any prime p and integer a, a²-1 = 1 mod p. It happens that the converse to FLT is often but not always true. That is, if n is composite and a is an integer, then more often than not an−1‡1_mod n. We can use this as the basis of a simple primality test, called the Fermat Test. For a € Zn we make the following definitions. 1) We call a a Fermat Liar for n if a^−1 = 1_mod n, where a ‡ (0, 1, n − 1). 2) We call a a Fermat Witness for n if an−¹ ‡1_mod n, where a ‡ (0, 1, n − 1). - If a number is composite, then 2 is very often a Fermat Witness. What is the smallest composite integer n greater than 4157 for which 2 is not a Fermat Witness?
Related questions
Question
Transcribed Image Text:This question concerns primality testing.
Recall Fermat's Little Theorem:
For any prime p and integer a, aº-1 = 1 mod p.
It happens that the converse to FLT is often but not
always true.
That is, if n is composite and a is an integer, then more
often than not an #1 mod n.
.n-1
We can use this as the basis of a simple primality test,
called the Fermat Test.
For a € Zn we make the following definitions.
'n
n-1 = 1 mod n,
1) We call a a Fermat Liar for n if an
where a & (0, 1, n − 1).
2) We call a a Fermat Witness for n if
an−¹ ‡1 mod n, where a ‡ (0, 1, n − 1).
If a number is composite, then 2 is very often a Fermat
Witness.
What is the smallest composite integer n greater than
4157 for which 2 is not a Fermat Witness?
Expert Solution
This question has been solved!
Explore an expertly crafted, step-by-step solution for a thorough understanding of key concepts.
This is a popular solution!
Trending now
This is a popular solution!
Step by step
Solved in 3 steps
