CS70-Homework 4 Solved

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.

(a)   2x ≡ 5 (mod 15)

(b)   2x ≡ 5 (mod 16) (c) 5x ≡ 10 (mod 25)

2        Euclid’s Algorithm
(a)    Use Euclid’s algorithm from lecture to compute the greatest common divisor of 527 and 323. List the values of x and y of all recursive calls.

(b)   Use extended Euclid’s 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.

(c)    Find x (mod 27) if 5x+26 ≡ 3 (mod 27). You can use the result computed in (b).

(d)   Assume a, b, and c are integers and c 0. 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:

(a)    132018 (mod 12)

(b)   811111 (mod 9)

(c)    7256 (mod 11)

(d)   3160 (mod 23)

4        Euler’s Totient Function
Euler’s 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 Euler’s totient function that you can use without proof:

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

(a)    Let p be a prime number. What is φ(p)?

(b)   Let p be a prime number and k be some positive integer. What is φ(pk)?

(c)    Let p be a prime number and a be a positive integer smaller than p. What is aφ(p) (mod p)? (Hint: use Fermat’s Little Theorem.)

(d)   Let b be a positive integer whose prime factors are p1, p2,..., pk. We can write b  p  ... pαkk.

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

∀i ∈ {1,2,...,k}, aφ(b) ≡ 1 (mod pi)

5        FLT Converse
Recall that the FLT states that, given a prime n, an−1 ≡ 1 (mod n) for all 1 ≤ a ≤ n−1. Note that it says nothing about when n is composite.

Can the FLT condition (an−1 ≡ 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, let’s define

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

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

(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 an−1 ≡6 1 (mod n).

(b)   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 an−1 ≡6 1 (mod n), we can find at least |S(n)|/2 such a. (Hint: You’re 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 doesn’t rule out the possibility that some composite number n satisifes the FLT condition entirely: for all a relatively prime to n, an−1 ≡ 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.

(c)    First, show that if a ≡ b mod m1 and a ≡ b mod m2, with gcd(m1,m2) = 1, then a ≡ b (mod m1m2).

(d)   Let n = p1p2 ··· pk where pi are distinct primes and pi −1 | n−1 for all i. Show that an−1 ≡ 1 (mod n) for all a ∈ S(n)

(e)    Verify that for all a coprime with 561, a560 ≡ 1 (mod 561).