Assignment # 3 Solution

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