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 n² divides n+6.

Solution. Write , 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 ≤ i ≤ p-1, there exists a unique 1 ≤ j ≤ p-1 such that ij ≡ 1 (mod p). [ Apply Bezout’s identity to i and p. ] Furthermore, i = j if and only if i² ≡ 1 (mod p), if and only if i² – 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 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 2^m – 1 and 2ⁿ+1 are coprime. (Does this ring a bell?)

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

• ;
• .

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

Problem 4. Classify all solutions of x² + y² = z², 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 g² 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 x² ≡ y² ≡ 1 (mod 8 ), so z² ≡  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 x² = z²– y² = (z+y)(z–y). Since x is even, write x = 2x’, which gives:

Now the two terms and 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):

From , we thus write , or . Putting back the common divisor (x, y) we get:

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 (b ≠ a), 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 aⁿ = (1 + nk)ⁿ 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 y² + (y+d)² = d³. 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.