# quite hard:

genius
Posers and Puzzles 30 Nov '02 18:43
1. genius
Wayward Soul
30 Nov '02 18:43
let N be a positive interger less than 10^2002. when the digit 1 is
placed after the last digit of N, the number formed is three times the
number formed when the digit 1 is placed infront of N. How many
different values of N are there???

but it's even harder without a calculator...i had to do this for a maths
challenge in school, without a calculator-argh!!!

mr genius
2. Acolyte
Now With Added BA
01 Dec '02 12:49
let N be a positive interger less than 10^2002. when the digit 1 is
placed after the last digit of N, the number formed is three times the
number formed when the digit 1 is placed infront of N. How many
different values of N are there???

but it's even harder without a calculator...i had to do this for a maths
challenge in school, witho...
I think the answer is 333, and I did not use a calculator, just pen and paper. Here's my
reasoning:

3(10^x + N) = 10N + 1
=&gt; 7N = 3*10^x - 1

So 3*10^x -1 must be divisible by 7.

As it turns out, 3*10^x - 1 is divisible by 7 if and only if x is of the form 6y - 1. I worked
this out by calculating 3*10^n modulo 7 for n = 1 to 5; 10^6 = 1 (mod 7) (by Fermat's Little
Theorem ðŸ˜› ) so x can be considered modulo 6. Hence the result, since for n=1 to 5, only
3*10^5 = 1 (mod 7).

Anyway, there are 333 such numbers &lt;= 2002 (3*10^2003 -1 &gt; 7*10^2002, so that's not
allowed.)

If you've haven't done modular arithmetic, what it means for two numbers to be congruent
(mod n) is that they differ only by a multiple of n. This is pretty nifty, as it means you can
throw away multiples of n all over the place.
3. Acolyte
Now With Added BA
01 Dec '02 12:51
PS: I'm going to be examined on this kind of stuff at the end of the year. Calculators are
almost certainly NOT permitted.
4. genius
Wayward Soul
02 Dec '02 16:41
nope-we haven't done the modular stuff. i did the question only really
with algebra, but with the same reasoning. also, wasn't fermat's last
therom proved right, in that a^n+b^n &lt;&gt; c^n if a,b,c &amp; n are positive
intergers, and n is greater than 2? therefore, if it's doesn't work, what
can it be used for???

G
5. 02 Dec '02 17:04
Genius, Acolyte used something called Fermat's Little Theorem, not
Fermat's Last Theorem.

The Little Theorem (discovered/created? in 1640) is far more useful
than the more well-known Last Theorem. It is often used (amongst
many other things) for testing the primality of numbers. However,
because the proof goes only one way it is what's called 'necessary but
not sufficient'. This means that it holds for all primes, but (sadly!)
also holds for some composite numbers too.

Fermat's Little Theorem says that if n is a prime number, and
(a,n) = 1, then a^(n-1) = 1 (mod n).

Modular/Modulo arithmetic (and some of the results contained
therein) is an extraordinarily powerful idea, reducing calculations with
huuuuge numbers to quite basic problems. It really is an astonishing
tool.

To find out more on Modular arithmetic (there are loads of sites
dealing with it) you could do worse than going to:-

http://www.cut-the-knot.com/blue/Modulo.shtml

To see the proof of Fermat's Little Theorem visit:-

http://www.utm.edu/research/primes/notes/proofs/FermatsLittleTheore
m.html

Mark

6. 02 Dec '02 17:06
Should add that (a,n) = 1 means the greatest common divisor of a
and n is 1. That is, n (a prime) does not divide (the integer) a.

Mark
7. Acolyte
Now With Added BA
02 Dec '02 22:23
We tried to find some n such that (a,n) = 1 =&gt; a^n-1 = 1 (mod n) in one of my supervisions
recently, but got stuck. Maybe that should be a puzzle in its own right.