Written Assignment #3 Solution

Description

Q.1 What are the prime factorizations of

1. 511

2. 8085

3. 12!

1. Use Euclidean algorithm to nd gcd(267; 79).

2. Find integers s and t such that gcd(267; 79) = 79s + 267t.

3. Use Euclidean algorithm to nd gcd(561; 234).

4. Find integers s and t such that gcd(561; 234) = 234s + 561t.

1. If cj(a b), then cj(a gcd(b; c)).

2. Suppose that gcd(a; y) = d₁ and gcd(b; y) = d₂. Prove that gcd(gcd(a; b); y) = gcd(d₁; d₂):

(c) Suppose that gcd(b; a) = 1. Prove that gcd(b + a; b a) 2.

Q.4

1. State Fermat’s little theorem.

2. Show that Fermat’s little theorem does not hold if p is not prime.

3. Computer 302³⁰² (mod 11), 4762⁵³⁶⁷ (mod 13), 2³⁹⁶⁷⁴ (mod 523).

1

Q.5 Given an integer a, we say that a number n passes the \Fermat primality test (for base a)” if a^{n 1} 1 (mod n).

1. For a = 2, does n = 561 pass the test?

2. Did the test give the correct answer in this case?

Q.6 Solve the following modular equations.

1. 267x 3 (mod 79).

2. 778x 10 (mod 379).

3. 312x 3 (mod 97).

Q.7 Let a and b be positive integers. Show that gcd(a; b) + lcm(a; b) = a + b if and only if a divides b, or b divides a.

Q.8 Prove that if a and m are positive integer such that gcd(a; m) = 1 then the function

f : f0; : : : ; m 1g ! f0; : : : ; m 1g

de ned by

f(x) = (a x) mod m

is a bijection.

Q.9 Prove that if a and m are positive integers such that gcd(a; m) 6= 1 then a does not have an inverse modulo m.

Q.10 Prove that if m is a positive integer of the form 4k + 3 for some non-negative integer k, then m is not the sum of the squares of two integers.

Q.11 Find counterexamples to each of these statements about congruences.

1. If ac bc (mod m), where a; b; c, and m are integers with m 2, then a b (mod m).

2. If a b (mod m) and c d (mod m), where a; b; c; d, and m are integers with c and d positive and m 2, then a^c b^d (mod m).

Q.12 Convert the decimal expansion of each of these integers to a binary expansion.

(a) 321 (b) 1023 (c) 100632

Q.13 Show that log₂ 3 is an irrational number. Recall that an irrational number is a real number x cannot be written as the ratio of two integers.

Q.14 Prove that there are in nitely many primes of the form 4k + 3, where k is a nonnegative integer. [Hint: Suppose that there are only nitely many such primes q₁; q₂; : : : ; q_n, and consider the number 4q₁q₂ q_n 1.]

Q.15 Solve the system of congruence x 3 (mod 6) and x 4 (mod 7) using the methods of Chinese Remainder Theorem or back substitution.

Q.16 Find all solutions, if any, to the system of congruences x 5 (mod 6), x 3 (mod 10), and x 8 (mod 15).

Q.17 Show that we can easily factor n when we know that n is the product of two primes, p and q, and we know the value of (p 1)(q 1).

3