Please turn on javascript in your browser to play chess.
Posers and Puzzles

Posers and Puzzles

  1. Standard member 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. Donation 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
    => 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 <= 2002 (3*10^2003 -1 > 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. Donation 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. Standard member 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 <> c^n if a,b,c & 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. Donation Acolyte
    Now With Added BA
    02 Dec '02 22:23
    We tried to find some n such that (a,n) = 1 => 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.