Elementary Number Theory, ISBN numbers and mathematics olympiads

Question 1:

The International Standard Book Number (ISBN) used in many libraries consists of nine digits a_{1} a_{2}\ldots a_{9} followed by a tenth check digit a_{10} (somewhat like Hamming codes), which satisfies

a_{10} = \sum_{k=1}^{9}k a_{k} \pmod {11}

Determine whether each of the ISBN’s below is correct.
(a) 0-07-232569-0 (USA)
(b) 91-7643-497-5 (Sweden)
(c) 1-56947-303-10 (UK)

Question 2:

When printing the ISBN a_{1}a_{2}\ldots a_{9}, two unequal digits were transposed. Show that the check digits detected this error.

Remark: Such codes are called error correcting codes and are fundamental to wireless communications including cell phone technologies.

More later,
Nalin Pithwa.

Any integer can be written as the sum of the cubes of 5 integers, not necessarily distinct

Question: Prove that any integer can be written as the sum of the cubes of five integers, not necessarily.

Solution:

We use the identity 6k = (k+1)^{3} + (k-1)^{3}- k^{3} - k^{3} for k=\frac{n^{3}-n}{6}=\frac{n(n-1)(n+1)}{6}, which is an integer for all n. We obtain

n^{3}-n = (\frac{n^{3}-n}{6}+1)^{3} + (\frac{n^{3}-n}{6}-1)^{3} - (\frac{n^{3}-n}{6})^{3} - (\frac{n^{3}-n}{6}).

Hence, n is equal to the sum

(-n)^{3} + (\frac{n^{3}-n}{6})^{3} + (\frac{n^{3}-n}{6})^{3} + (\frac{n-n^{3}}{6}-1)^{3}+ (\frac{n-n^{3}}{6}+1)^{3}.

More later,
Nalin Pithwa.

A random collection of number theory problems for RMO and CMI training

1) Find all prime numbers that divide 50!

2) If p and p^{2}+8 are both prime numbers, prove that p^{3}+4 is also prime.

3) (a) If p is a prime, and p \not|b, prove that in the AP a, a+b, a+2b, a+3b, \ldots, every pth term is divisible by p.

3) (b) From part a, conclude that if b is an odd integer, then every other term in the indicated progression is even.

4) Let p_{n} denote the nth prime. For n>5, show that p_{n}<p_{1}+p_{2}+ \ldots + p_{n-1}.

Hint: Use induction and Bertrand's conjecture.

5) Prove that for every n \geq 2, there exists a prime p with p \leq n < 2p.

More later,
Regards,
Nalin Pithwa

Find the last two digits of 9^{9^{9}}

Here is a cute example of the power of theory of congruences. Monster numbers can be tamed !!

Question :

Find the last two digits of 9^{9^{9}}.

Solution:

A famous mathematician, George Polya said that a good problem solving technique is to solve an analagous less difficult problem.

So, for example, if the problem posed was “find the last two digits of 2479”. How do we go about it? Find the remainder upon division by 100. Now, how does it relate to congruences ? Modulo 100 numbers !

So, the problem reduces to — find out 9^{9^{9}} \equiv 9 \pmod {10}.

Now, what is the stumbling block…the exponent 9^{9} makes the whole problem very ugly. But,

9^{9} \equiv 9 \pmod {10}, which means 9^{9}-9=10k, that is, 9^{9} = 9 + 10k,

also, use the fact 9^{9} \equiv 89 \pmod {100}

Hence, 9^{9^{9}}=9^{9+10k} = 9^{9}.9^{10k}

9^{9^{9}} \pmod {100}  = 9^{9}.9^{10k} \pmod {100} \equiv 89. 9^{10k} \pmod {100}

So, now we need to compute 9^{10k} \pmod {100} = (9^{10})^{k} \pmod {100} = (89.9)^{k} \pmod {100} = 89^{k}. 9^{k} \pmod {100}

Hence, 9^{9^{9}} \pmod {100} \equiv 89^{k+1}.9^{k} \pmod {100} \equiv (89.9)^{k}.89 \pmod {100} \equiv (1)^{k}.89 \pmod {100} \equiv 89 \pmod {100}.

-Nalin Pithwa.