Q.1 What are the prime factorizations of
(a) 511
(b) 8085
(c) 12!
(a) Use Euclidean algorithm to nd gcd(267; 79).
(b) Find integers s and t such that gcd(267; 79) = 79s + 267t.
(c) Use Euclidean algorithm to nd gcd(561; 234).
(d) Find integers s and t such that gcd(561; 234) = 234s + 561t.
(a) If cj(a b), then cj(a gcd(b; c)).
(b) Suppose that gcd(a; y) = d1 and gcd(b; y) = d2. Prove that gcd(gcd(a; b); y) = gcd(d1; d2):
(c) Suppose that gcd(b; a) = 1. Prove that gcd(b + a; b a) 2.
Q.4
(a) State Fermat’s little theorem.
(b) Show that Fermat’s little theorem does not hold if p is not prime.
(c) Computer 302302 (mod 11), 47625367 (mod 13), 239674 (mod 523).
1
Q.5 Given an integer a, we say that a number n passes the \Fermat primality test (for base a)" if an 1 1 (mod n).
(a) For a = 2, does n = 561 pass the test?
(b) Did the test give the correct answer in this case?
Q.6 Solve the following modular equations.
(a) 267x 3 (mod 79).
(b) 778x 10 (mod 379).
(c) 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.
(a) If ac bc (mod m), where a; b; c, and m are integers with m 2, then a b (mod m).
(b) 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 ac bd (mod m).
2
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 log2 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 q1; q2; : : : ; qn, and consider the number 4q1q2 qn 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
