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*^{2} 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*^{2} ≡ 1 (mod *p*), if and only if *i*^{2} – 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^{n}+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^{n}+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^{n}+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^{n}+1 are odd. Hence *g* = 1. ♦

**Problem 4**. Classify all solutions of *x*^{2} + *y*^{2} = *z*^{2}, 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*^{2} 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*^{2} ≡ *y*^{2} ≡ 1 (mod 8 ), so *z*^{2} ≡ 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*^{2} = *z*^{2}– *y*^{2} = (*z*+*y*)(*z*–*y*). Since *x* is even, write *x* = 2*x’*, 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. 🙂

- [Hint start] Since
*a*is 1 mod*n*, we can write*a*= 1 +*nk*for some integer*k*. Now expand*a*= (1 +^{n}*nk*)via binomial expansion. Look at lower terms. [Hint end]^{n} - [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] - [Hint start] Induction on
*k*. Good exercise on induction if you’re new to such techniques. [Hint end] - [Hint start] Write
*d*=*x-y*. Rewrite equation as*y*^{2}+ (*y*+*d*)^{2}=*d*^{3}. Expand and complete the square on the left, leaving only terms depending on*d*… [Hint end] - [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 2*n*but not*n*(why?)…. [Hint end]

That’s all.

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

Well, “hard” is relative. But seriously, Q1 is obviously much simpler than Q5. 🙂