MA357, Spring 2008
Comments on Problem Set 2

a. If d|(a+b) and d|(a–b) then, taking the sum and difference, we see that d|(2a) and d|(2b). So consider two cases:

• If d is even, say d = 2u. Then it follows that u|a and u|b, hence, given our assumption, that u=1 (or –1, but gcds are positive). Hence, d=2.

• If d is odd, then gcd(d,2) = 1, and we can conclude that d|a and d|b, and hence that d=1.

  Let me repeat the crucial point that it's not enough to note that d doesn't divide 2. After all, 4 doesn't divide 2, and 4|2x most certainly doesn't imply that 4|x. (Try x=6, for example.)

Can we do it using linear combinations? Well, we're given that gcd(a,b) = 1, so we know we can find r and s such that ar + bs = 1. Suppose we try to find x and y such that (a+b)x + (a–b)y = 1. This equation turns into a(x+y) + b(x–y) = 1, so we want x + y = r, x – y = s, which works out to x = (r+s)/2 and y = (r–s)/2. If r and s are both odd, we can do that, and we get gcd(a+b,a–b) = 1. Otherwise, taking x = r+s and y = r–s gives (a+b)x + (a–b)y = 2, and the gcd is either 1 or 2.

b. If d|a and d|(a+b), then d|b, so d=1.

Alternatively, given ar + bs = 1, we have a(r–s) + (a+b)s = 1.

c. Clearly 2 is a common divisor. To show that it is the greatest common divisor, argue as in (a): any odd common divisor must be either 1 or –1, and any even common divisor must be either 2 or –2. So the gcd is 2.

Linear combinations work too: from ax + by = 1, we get (2a)x + (2b)y = 2, and it follows that the gcd is either 1 or 2. Since 2 clearly is a common divisor, it must be the gcd.

d. Again, either 1 or 2, depending on whether b is even or not.

Note: these arguments use the definition of the gcd directly or the connection with linear combinations. They avoid using unique factorization. Considering we hadn't yet proved unique factorization when you were assigned this problem set, that seems the way to go. But the most important thing is this: if you use an argument that depends on unique factorization, you should demonstrate that you know that by saying so!

2. If r divides a=n!+1 and b=(n+1)!+1, then r also divides a(n+1)–b=n. But if r divides n, it divides n!. So r divides both n! and n!+1, hence divides their difference, which is 1. Hence r=1.

It's probably possible to find an explicit linear combination that's equal to 1, but it's too much effort.

3. These are all easy, but they illustrate an important technique coming from division with remainder:

a. Dividing any integer n by 2 allows us to write it as n = 2q + r, where r must be either 0 or 1. If n is odd, we must have r = 1, and hence any odd number can be written (uniquely, even) as 2q + 1. So we can write the two odd numbers in question as 2q + 1 and 2r + 1, and add them to get 2(q + r + 1), which is even.

b. Similarly, we know n = 2q + 1, hence

n² = 4q² + 4q + 1 = 4(q² + q) + 1

c. This time we divide n by 3 to get that n = 3q + 1 or n = 3q + 2. Computing n² – 1 in either case shows that the answer is divisible by 3.

4. There are lots of ways to attack this one; here are some

• Prime Factorization: if x and y are integers and x² = 2y², then the prime factorization of the left hand side has an even number of primes in it (i.e., twice the number appearing in the factorization of x, because it's just the factorization of x written twice), and the right hand side has an odd number of primes in it (twice the number in the factorization of y, plus the "2"). This contradicts unique factorization.

• Descent: suppose there is a solution with x and y positive. Then the equation implies that 2|x and 2|y. Putting x = 2r, y = 2s, we get r² = 2s², so that the pair (r,s) is a smaller solution of the same equation, and both r and s are still positive integers. But now we can apply the same reasoning to r and s to obtain a still smaller solution, and so on. This is impossible, because there are only a finite number of positive integers smaller than x.

• Lowest Terms: we can assume x and y are relatively prime, since any common factors can be eliminated from both sides of the equation. But then the same reasoning as before shows that 2|x and 2|y, which is a contradiction.

How would you generalize these methods to handle the case when we replace 2 by some other non-square integer?

5. This one is basically just work: follow the algorithm, and it comes out. We get that gcd(771769, 32378) = 1, and taking x = –14281, y = 340405 makes 771769x + 32378y = 1 (another solution is x = 18097, y = –431364).

It might be worth pointing out that several computer programs do this automagically. For example, the "gp" program has a command called "bezout" which does this computation, so that entering "bezout(771769,32378)" at the gp prompt yields the answer "[–14281,340405,1]". See the note on GP.

6. The boils down (!) to solving the equation 5x + 11y = 3. Taking x = 5 and y = –2 works, as does taking x = –6 and y = 3. Both solutions can easily be translated into little stories about egg timers.

7. You want to avoid working with fractions, so plug in u/v and multiply by vⁿ to clear denominator. Rearranging, we get that u|a₀vⁿ and v|a_nuⁿ. But the fraction is in lowest terms, i.e., gcd(u,v)=1, so that the theorem we proved in class says that if u|xv, then u|x (and the same with u and v reversed). Applying this repeatedly allows us to peel off all the v's in one case and all the u's in the other, and we get where we want to get.

8. Again, we can easily find counterexamples:

? for(k=1,40,print(k,"   ",factor(6*k-1),"   ",factor(6*k+1)))
1    [5, 1]            [7, 1]
2    [11, 1]           [13, 1]
3    [17, 1]           [19, 1]
4    [23, 1]           [5, 2]
5    [29, 1]           [31, 1]
6    [5, 1; 7, 1]      [37, 1]
7    [41, 1]           [43, 1]
8    [47, 1]           [7, 2]
9    [53, 1]           [5, 1; 11, 1]
10   [59, 1]           [61, 1]
11   [5, 1; 13, 1]     [67, 1]
12   [71, 1]           [73, 1]
13   [7, 1; 11, 1]     [79, 1]
14   [83, 1]           [5, 1; 17, 1]
15   [89, 1]           [7, 1; 13, 1]
16   [5, 1; 19, 1]     [97, 1]
17   [101, 1]          [103, 1]
18   [107, 1]          [109, 1]
19   [113, 1]          [5, 1; 23, 1]
20   [7, 1; 17, 1]     [11, 2]
21   [5, 3]            [127, 1]
22   [131, 1]          [7, 1; 19, 1]
23   [137, 1]          [139, 1]
24   [11, 1; 13, 1]    [5, 1; 29, 1]
25   [149, 1]          [151, 1]
26   [5, 1; 31, 1]     [157, 1]
27   [7, 1; 23, 1]     [163, 1]
28   [167, 1]          [13, 2]
29   [173, 1]          [5, 2; 7, 1]
30   [179, 1]          [181, 1]
31   [5, 1; 37, 1]     [11, 1; 17, 1]
32   [191, 1]          [193, 1]
33   [197, 1]          [199, 1]
34   [7, 1; 29, 1]     [5, 1; 41, 1]
35   [11, 1; 19, 1]    [211, 1]
36   [5, 1; 43, 1]     [7, 1; 31, 1]
37   [13, 1; 17, 1]    [223, 1]
38   [227, 1]          [229, 1]
39   [233, 1]          [5, 1; 47, 1]
40   [239, 1]          [241, 1]

Looking at the list confirms that the assertion is false, though the first counterexample happens only when k=20. The other thing we see is that the counterexamples aren't all that frequent, so we need to be smart to prove that there are infinitely many of them.

The proof I like is based on the idea that it's easier to prove what we want if we replace "is composite" by something more specific. For example, suppose we want to find k such that 6k–1 is divisible by 5, and 6k+1 is divisible by 7. Of course k=1 works, because we get exactly 5 and 7. If we can find other k's that do this, then both 6k–1 and 6k+1 will have to be composite. To do that, note that the difference between 6(k + 35) – 1 and 6k – 1 is divisible by 5, and that the difference between 6(k + 35) + 1 and 6k + 1 is divisible by 7. (Both differences are equal to 6x35 = 210, of course.) It follows that for any integer x if we take n = 1 + 35x we will have 6n – 1 divisible by 5 and 6n + 1 divisible by 7, and so (except when x = 0) neither will be prime. This is basically a congruence argument: we are "pasting together" a congruence mod 5 and a congruence mod 7 to get a congruence mod 35.

One can do the same thing by taking n = 2 + 143x, for example. This time the crucial divisors are 11 and 13. The apparent rarity of counterexamples is just a consequence of the fact that these sequences have long periods. For large n, it's more likely than not that neither 6n – 1 nor 6n + 1 will be prime. On the other hand, it seems likely that every so often one of them will indeed be prime. Are there infinitely many primes for which one of the two expressions gives a prime?

9. We first need to solve 15r + 7s = 1, which, fortunately, is easy: r = 1, s = –2. Now we just scale everything by 310. Hence a first solution is x = 310, y = –620. The general solution then is

10. This was the hardest one! Here are two possible ways to do it:

Slick argument: Let L be the product of all the odd numbers up to n, let k be the largest integer such that 2^k is less than or equal to n, and let M = 2^k–1L. Consider the product MS, term by term:

• If m is less than or equal to n and is not equal to 2^k, then it is either 2^a for some a < k or it is 2^ax with x odd. We need to see that in the latter case we must have a < k also. Indeed, if a = k and x > 1 then 2^kx > 2^k * 2 = 2^k+1 > n. Hence, in all of these cases M * (1/m) is an integer.

• The only other m is 2^k itself. But M * 2^k = (odd)/2, and hence is not an integer.

Step-by-step argument We first need to prove a Lemma, which is easy so I will leave the proof to you. If p is a prime number, we'll say something is exactly divisible by p^a if it is divisible by p^a but not by p^a+1.

Lemma If we add two fractions in lowest terms, one with denominator exactly divisible by 2^a and the other with denominator not divisible by 2^a, then the sum, in lowest terms, has denominator exactly divisible by 2^a.

Now it's an easy induction argument to show that at each step we are always in the situation of the Lemma. Since we start with 1/2 and each step, according to the Lemma, will either make the denominator more divisible by 2 (if the new term is the one divisible by 2^a) or keep it just as divisible as it was before (if not), the sum will never be an integer.

(The crucial bit of the argument is similar to the estimates we did for the slick part: it works because 2^k+1 sits between 2^k and the next number with the same number of twos in the denominator, namely 3*2^k.)

By the way, one can also make an argument based on showing that if p is a prime between n/2 and n, then p divides the denominator but not the numerator of the sum. This is pretty straightforward provided one knows that such a p exists. Do you think one always does? Why?