Sample Problem Solving + Homework Hints

In this post, I’ll talk about basic number theory again. But I’ll still assume you already know modular arithmetic. 🙂  In the first part, there’ll be some sample solutions for number theoretic problems, some of which were already presented in class; in the second part, I’ll give hints for the homework on 12 Nov 2011.

Problem 1. Find all positive integers n for which n2 divides n+6.

Solution. Write \frac {n^2}{n+6} = n - 6 + \frac{36}{n+6}, so n+6 must divide 36, i.e. n+6 is a factor of 36 which is greater than 6. The only such factors are 9, 12, 18, 36. Hence n = 3, 6, 12, 30. ♦

Problem 2. (Wilson’s theorem) Prove that if p is prime, then (p-1)! ≡ -1 (mod p).

Solution. This is clearly true for p=2, 3. Assume p > 3. Consider the elements 1, 2, …, p-1. For each 1 ≤ ip-1, there exists a unique 1 ≤ jp-1 such that ij ≡ 1 (mod p). [ Apply Bezout’s identity to i and p. ] Furthermore, i = j if and only if i2 ≡ 1 (mod p), if and only if i2 – 1 = (i+1)(i-1) is a multiple of p, i.e. if and only if i ≡ ±1 (mod p). So other than the elements 1 and p-1, the other p-3 elements can be paired into \frac{p-3} 2 pairs which are mutually inverse modulo p. Hence, the product of 1, 2, …, p-1 modulo p is 1×(p-1) ≡ -1 (mod p). ♦

Example. Consider p = 11. Then modulo 11, the elements {2,3,…,9} can be paired via {2, 6}, {3, 4}, {5, 9}, {7, 8}, where the product of each pair is 1 mod 11. So the product of 1-10 is 1×10 ≡ -1 (mod 11).

Problem 3. Prove that if m, n are positive integers with m odd, then 2m – 1 and 2n+1 are coprime. (Does this ring a bell?)

Solution. Here’s a more classical proof. Suppose g is a common divisor of both 2m – 1 and 2n+1. Now consider the following two elements:

  • 2^{mn} - 1 = (2^m - 1)(2^{m(n-1)} + 2^{m(n-2)} + \ldots + 1);
  • 2^{mn} + 1 = (2^n+1)(2^{n(m-1)} - 2^{n(m-2)} + \ldots + 1).

[ These equalities  follow from the factorisations of X^n - 1, and (when m is odd) X^m + 1. ]  Since g divides 2m – 1 and 2n+1, it must divide both numbers above and hence their difference, which is 2. But g cannot be 2 since 2m – 1 and 2n+1 are odd. Hence g = 1. ♦

Problem 4. Classify all solutions of x2 + y2 = z2, for positive integers x, y, z. [ The ordered triplet (x, y, z) is called a Pythagorean triplet. ]

Solution. If g|x and g|y, then g|z as well so dividing by g2 in the above relation, we might as well assume (x, y) = 1. Likewise, we can assume (y, z) = (z, x) = 1. Next consider x, y mod 2. We already know they can’t be both even since (x, y) = 1. But if they were both odd then x2y2 ≡ 1 (mod 8 ), so z2 ≡  2 (mod 8 ) is divisible by 2 but not by 4, which is impossible for a square. Thus, x and y are of different parity; assume x is even, y is odd.

This gives x2 = z2y2 = (z+y)(zy). Since x is even, write x = 2x’, which gives:

x'^2 = \left(\frac{z+y} 2\right) \left(\frac{z-y} 2\right).

Now the two terms \frac{z+y}2 and \frac{z-y}2 must be coprime: because any common divisor g would then divide the sum (which is z) and the difference (which is y), thus contradicting our assumption that (y, z) = 1. Since we have two coprime numbers whose product is a square, each of these numbers must itself be a square (you might want to try proving this as an exercise, by considering the prime factorisations of the numbers):

\frac{z+y}2 = a^2, \quad \frac{z-y}2 = b^2 \implies z = a^2+b^2, y = a^2-b^2.

From x'^2 = a^2 b^2, we thus write x' = ab, or x = 2ab. Putting back the common divisor (x, y) we get:

x = 2gab, y = g(a^2 - b^2), z = g(a^2 + b^2),

where (a, b)=1 and a > b are not both odd.♦

Hints for Homework (12 Nov 2011)

To avoid spoiling problem a for you while you’re reading the hint for problem b (ba), I’ve placed the hints in white text. Highlight the appropriate area to view the hint. 🙂

  1. [Hint start] Since a is 1 mod n, we can write a = 1 + nk for some integer k. Now expand an = (1 + nk)n via binomial expansion. Look at lower terms. [Hint end]
  2. [Hint start] Clearing denominators gives z(x+y) = xy. Let g = gcd(x, y). Write x = gx’ and y = gy’ where (x’, y’) = 1. This gives z(x’+y’) = gx’y’. Look closely at x’+y’. [Hint end]
  3. [Hint start] Induction on k. Good exercise on induction if you’re new to such techniques. [Hint end]
  4. [Hint start] Write d = x-y. Rewrite equation as y2 + (y+d)2 = d3. Expand and complete the square on the left, leaving only terms depending on d [Hint end]
  5. [Hint start] This one is probably the hardest: let p be the smallest prime factor of n (assuming n>1). Clearly p is odd, so we let d be the multiplicative order of 2 modulo p. Then d divides (p-1), divides 2n but not n (why?)…. [Hint end]

That’s all.

This entry was posted in Notes and tagged , , , , , . Bookmark the permalink.

2 Responses to Sample Problem Solving + Homework Hints

  1. Eugene Lee says:

    Funny how you said 5 was the hardest, because it was one of the first I solved. :p

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s