Before you start your homework, state briefly how you worked on it. Who else did you work with? List names and email addresses. (In case of homework party, you can just describe the group.)

Find all solutions (modulo the corresponding modulus) to the following equations. Prove that there are no other solutions (in a modular setting) to each equation.

• 2x 5 (mod 15)
• 2x 5 (mod 16) (c) 5x 10 (mod 25)

2 Euclids Algorithm

• Use Euclids algorithm from lecture to compute the greatest common divisor of 527 and 323. List the values of x and y of all recursive calls.
• Use extended Euclids algorithm from lecture to compute the multiplicative inverse of 5 mod

27. List the values of x and y and the returned values of all recursive calls.

• Find x (mod 27) if 5x+26 3 (mod 27). You can use the result computed in (b).
• Assume a, b, and c are integers and c > Prove or disprove: If a has no multiplicative inverse mod c, then ax b (mod c) has no solution.

3 Modular Exponentiation

Compute the following:

• 13²⁰¹⁸ (mod 12)
• 8¹¹¹¹¹ (mod 9)
• 7²⁵⁶ (mod 11)
• 3¹⁶⁰ (mod 23)

4 Eulers Totient Function

Eulers totient function is defined as follows:

(n)= |{i : 1 i n,gcd(n,i)= 1}|

In other words, (n) is the total number of positive integers less than or equal to n which are relatively prime to it. Here is a property of Eulers totient function that you can use without proof:

For m,n such that gcd(m,n) = 1, (mn)=(m)(n).

• Let p be a prime number. What is (p)?
• Let p be a prime number and k be some positive integer. What is (p^k)?
• Let p be a prime number and a be a positive integer smaller than p. What is a^(p) (mod p)? (Hint: use Fermats Little Theorem.)
• Let b be a positive integer whose prime factors are p₁, p₂,, p_k. We can write b p p_k^k.

Show that for any a relatively prime to b, the following holds:

i {1,2,,k}, a^(b) 1 (mod p_i)

5 FLT Converse

Recall that the FLT states that, given a prime n, aⁿ¹ 1 (mod n) for all 1 a n1. Note that it says nothing about when n is composite.

Can the FLT condition (aⁿ¹ 1 mod n) hold for some or even all a if n is composite? This problem will investigate both possibilities. It turns out that unlike in the prime case, we need to restrict ourselves to looking at a that are relatively prime to n. (Note that if n is prime, then every a < n is relatively prime to n). Because of this restriction, lets define

S(n)= {i : 1 i n,gcd(n,i)= 1},

so | S | is the total number of possible choices for a.

• Prove that for every a and n that are not relatively prime, FLT condition fails. In other words, for every a and n such that gcd(n,a) 6= 1, we have aⁿ¹ 6 1 (mod n).
• Prove that the FLT condition fails for most choices of a and n. More precisely, show that if we can find a single a S(n) such that aⁿ¹ 6 1 (mod n), we can find at least |S(n)|/2 such a. (Hint: Youre almost there if you can show that the set of numbers that fail the FLT condition is at least as large as the set of numbers that pass it. A clever bijection may be useful to compare set sizes.)

The above tells us that if a composite number fails the FLT condition for even one number relatively prime to it, then it fails the condition for most numbers relatively prime to it. However, it doesnt rule out the possibility that some composite number n satisifes the FLT condition entirely: for all a relatively prime to n, aⁿ¹ 1 mod n. It turns out such numbers do exist, but they were found through trial-and-error! We will prove one of the conditions on n that make it easy to verify the existence of these numbers.

• First, show that if a b mod m₁ and a b mod m₂, with gcd(m₁,m₂) = 1, then a b (mod m₁m₂).
• Let n = p₁p₂ p_k where p_i are distinct primes and p_i 1 | n1 for all i. Show that aⁿ¹ 1 (mod n) for all a S(n)
• Verify that for all a coprime with 561, a⁵⁶⁰ 1 (mod 561).