Number Theory (SK) October 21, 1998

1. Evaluate τ(360), ϕ(360), and σ(360).

2. Find (with proof) all primes that are one less than a fifth power.

3. List some numbers that are both triangular and square. (No proof necessary. Don’t give more than 6. If you can do that many I’ll believe you could go on forever.)

4. Find all solutions to 9x ≡ 6 (mod 24).

5. Find gcd(17119, 6519). Solve 17, 119x + 6, 519y = gcd(17119, 6519).

6. Given that one leg of a primitive Pythagorean triangle is 468, what are the possibilities for the lengths of the other two sides?

7. Prove that an even number is perfect if and only if it is of the form 2^{n−1}(2^{n} − 1) with 2^{n} − 1 a prime.

8. Prove that any odd prime, other than 5, divides infinitely many of the numbers 1, 11, 111, 1111, 11111, . . ..

9. Both of my kids love M&Ms, Sam has some interesting habits when eating them. He divides them up into piles by color, counts each pile, arranges the piles from smallest to largest, and then eats the piles in this order. (In case of a tie, he eats both (or all three) piles simultaneously, unless I can intervene before he crams them in.) Sam is particularly thrilled when the pile amounts are consecutive integers, e.g., 2 reds, 3 blues, 4 yellows, etc. Let us call a bag of M&Ms with consecutive integers for pile amounts a magic bag. As you know, Sam is also very fond of the powers of 2. Unfortunately these two obsessions can never coincide — no magic bag can contain 2^{n} M&Ms, in fact these are the only numbers not attainable. Prove both these facts (assume that the number of different colors of M&Ms is infinite).

10. Suppose we are given the system of linear congruences x ≡ a_{i} (mod n_{i}), 1 ≤ i ≤ k, with the n_{i} pairwise relatively prime. Define N_{i} = n_{1}n_{2} … n_{k}/n_{i}. Let x_{i} be the unique solution less than n_{i} to the congruence N_{i}x ≡ 1 (mod n_{i}). Prove that

X = ∑_{i=1}^{k} a_{i}N_{i}x_{i}

is a solution of the given system.