More Mods

What is the units digit for the number 123^(456) ?

Mod 3

Prove that if a^2+b^2 is a multiple of 3 then both a and b are multiples of 3.

Novemberish

a) A four digit number (in base 10) aabb is a perfect square. Discuss ways of systematically finding this number. (b) Prove that 11^{10}-1 is divisible by 100.

Check Code Sensitivity

Stage: 4 Challenge Level:

Well done Andrei Lazanu, age 14, School No. 205, Bucharest, Romania and Robert Goudie, age 17, Madras College, Fife, Scotland for these solutions.

I worked the problem considering two distinct possible errors: miscopying a single digit, and transposing two adjacent digits.

1. Miscopying a single digit
For a US Postal Service Money Order the condition for a valid number is:

$$a_1 + a_2 + . . . + a_{10} = a_{11} \ {\rm mod\ 9}.$$

Let's say the operator changes $a_n$ to $a_{n'}$ where these are any positive integers between 0 and 9. The condition the machine doesn't find the error is that the new number is also a valid money order number. So $a_n - a_{n'}\equiv 0 \hbox{ mod 9}$. This can happen only when the operator changes 0 with 9 or 9 with 0 for any digit including the first one (which could be 0). In all other cases the error will be found. Now I'll examine separately the case of the check digit. The same rule holds for it too, because I must look at the congruence mod 9, i.e. if there is an error in the check digit it is not detected by the machine if 0 is replaced by 9 or 9 by 0.

For an Airline Ticket, in order the machine does not find the error, the difference between the numbers obtained omitting the check digit, in the correct and in the miscopied form, must be a multiple of 7. But, if the difference of two numbers differing only in one digit is a multiple of 7, the numbers must differ by 7, 70, 700, 7000 ... and this means the difference of the two digits must be 7. The machine will not find the error if the operator changes 0 with 7, 1 with 8 or 2 with 9, or 7 with 0, 8 with 1, 9 with 2. The same is valid for the check digit too.