ASSIGNMENT 3 1. Illustrate the proof of Wilson’s Theorem with p = 17.2. Using Fermat’s Little...

Question

ASSIGNMENT 3 1. Illustrate the proof of Wilson’s Theorem with p = 17. 2. Using Fermat’s Little Theorem, find the remainder when 2^100 ; 000 is divided by 11. 3. Using Euler’s Theorem, find the...

1 answer below »

ASSIGNMENT 3
1. Illustrate the proof of Wilson’s Theorem with p = 17.
2. Using Fermat’s Little Theorem, find the remainder when 2^100;000 is divided by 11.
3. Using Euler’s Theorem, find the remainder when 5^100;000 is divided by 18.
4. Show that if n is odd and 3 does not divide n, then n2 = 1 (mod 24).
(Hint: It may help to note that 24 = 3 × 8.)
5. Evaluate ?(n), t (n) and s(n) for each n such that 25 = n = 30.
6. Prove that if n is odd, then t (n) = s(n) (mod 2).
7. Find the primes p and q if n = pq = 14647 and ?(n) = 14400.
8. What is the ciphertext that is produced when the RSA cipher with key e = 3, n =
3763 is used to encipher the message GO?
9. The next meeting of cryptographers will be held in the city of XXXXXXXXXXIt is known
that the cipher-text in this message was produced using the RSA cipher key e =
1997, n = 2669. Where will the meeting be held?
10. One of the oldest recorded cipher systems is the Caesar cipher, obtained by using
a cyclic shift of the letters of the alphabet. It is rather primitive compared to the
RSA system, and is easily broken. The following message was sent using this code.
Decipher the message, given that e is the most common letter in English.
UIF DIFFTF JT HPPE
Challenge problem
(a) If n is odd and (n, 5) = 1, show that 5 | (n4 + 4n).
(b) For which positive integers n is n4 + 4n prime?
Hint for (b): Deal with the case n even first. For n odd, factorise n4 + 4n as a product of
two terms by completing squares.

005_l1lnajo-eionjfcj.docx

Answered Same Day Dec 22, 2021

David · Accepted Answer

Question 1:Illustrate the proof of Wilson’s Theorem with p = 17.
Solution: Wilson’s theorem states that a number p is prime if and only if
		(p – 1)! = -1 (mod p)
Now, let’s prove it for p = 17
		(17 – 1)! = -1 (mod 17)
		16! = -1 (mod 17)
		(p – 1). (p – 2)! = -1 (mod 17)
		16. (p – 2)! = -1 (mod 17)
	Calculating (p – 2)! = 15!
	Solving it further, we get 16! = -1 (mod 17)
Question 2: Using Fermat’s Little Theorem, find the remainder when 2100,000 is divided by 11.
Solution: Fermat’s little theorem is as follows:
		np– 1 1 mod p
		210  1 mod 11
		210.10000  1100000 mod 11
		2100000 1 mod 11
The remainder would be 1.
Question 3: Using Euler’s Theorem, find the remainder when 5^100,000 is divided by 18.
Solution: According to the Euler’s theorem, 
	5 and 18 are relatively prime and ϕ(18) = 5
Thus, 55   1 mod 18
So, 5100000  (55)20000  120000 mod 18
Thus, the remainder is 1.
Question 4: Show that if n is odd and 3 does not divide n, then n2 ≡ 1 (mod 24).
(Hint:

ASSIGNMENT 3 1. Illustrate the proof of Wilson’s Theorem with p = 17. 2. Using Fermat’s Little Theorem, find the remainder when 2^100 ; 000 is divided by 11. 3. Using Euler’s Theorem, find the...

Solution

Answer To This Question Is Available To Download

Related Questions & Answers

Submit New Assignment