Computer Laboratory Home Page Search A-Z Directory Help
University of Cambridge Home Computer Laboratory
Hints for the exercises on factors
Computer Laboratory > Course material > Discrete Mathematics > Hints for the exercises on factors

Please do try the questions by yourself before resorting to these hints!

  1. False, false, and true. Now work out counter-examples for the first two and a proof for the third.
  2. Use Euclid's algorithm to show that 57.17 - 44.22 = 1 and 57.44 - 44.57 = 0.
  3. No.
    x = 437k - 308, y = 234 - 332k.
  4. x = -31 + 9r - 72s, y = 31 - 8r + 72s, z = -3 - 7s.
    Of course, it is possible to have a different particular solution offset by the complementary function, but there must be two degrees of freedom.
  5. 25.
  6. a|a and (a,b)|b so a.(a,b)|a.b and a|m. Write a = c.(a,b) and b = d.(a,b), and remember that (c,d) = 1. a|n so write n = e.a = e.c.(a,b), and write n = f.d.(a,b) similarly. Now m = a.b/(a,b) = c.d.(a,b) and n/(a,b) = e.c = f.d. c|n/(a,b) and d|n/(a,b), but (c,d) = 1 so c.d | n/(a,b) and m = c.d.(a,b) | n.
  7. Suppose there are only finitely many primes of the form 4k+3. Let pn be the largest of them and calculate N as in the question. N may be composite but its prime factors are all greater than pn and so they are all congruent to 1 modulo 4. So their product, N, is also congruent to 1 modulo 4. But it isn’t.
  8. The squares modulo 5 are 0, 1 and 4, so there is no α with N(α) = 2.
    4 = 2.2 and 4 = (1 + √5).(-1 + √5).
    Suppose α|2 and α|(1 + √5). Then N(α) = 1 or 4, since it can't be 2. So either α is a unit or 2 and (1 + √5) are both unit multiples of α.
  9. Square and add.
    WLoG, suppose (d,e)=k>1. Then k|f as well. d and e can not both be even (else f would be even giving a common factor of 2). d and e can not both be odd (else d²+e² ≡ 2 (mod 4) which could not be f²). d odd and e even makes f odd, so f+d and f-d are both even. 4g² = e² = f²-d² = (f+d)(f-d) = 2h.2i = 4hi. (h,i)|(h+i)=f and (h,i)|(h-i)=d but (f,d)=1. Consider prime factorization of g².
  10. Induction on k.
    fln = fn f(l-1)n+1 + fn-1f(l-1)n and use induction on l.
    (fn,fn-1) = (fn-1,fn-2) = ... =(f2,f1) = (1,1) = 1.
    fm = fnfm-n+1 + fn-1fm-n. Consider factors and replicate derivation of Euclid’s algorithm.
    fm | fmn and fn | fmn by above, but (fm,fn) = f(m,n) = f1 = 1, so fmfn | fmn.
  11. Worth thinking about efficiency: only test for odd factors (beyond 2), stop at √n, keep a list of primes and only test for divisibility by them.
  12. Define a function that takes two triples (r, s, t) from the extended Euclid’s algorithm and returns the next one.