Dismiss Notice
Join Physics Forums Today!
The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

Homework Help: Interesting number theory question

  1. Jul 13, 2007 #1
    1. The problem statement, all variables and given/known data
    For what natural numbers n is (10^n)-1 divisible by 73?


    2. Relevant equations
    N/A


    3. The attempt at a solution
    I have already found that it holds when n is a power of two greater than 8. (That means when n is great than 8, not the eigth power of 2)
    What other natural numbers n satisfy the above condition?
     
  2. jcsd
  3. Jul 13, 2007 #2

    Dick

    User Avatar
    Science Advisor
    Homework Helper

    How about 24,40,48 etc?
     
  4. Jul 13, 2007 #3
    Not sure how I got there but I think I have the right answer... thought it could be trivialized by Fermat's Little Theorem.

    [tex]10^{\phi(73)} \equiv 1 (mod 73)[/tex]
    since 73 is prime
    [tex]\phi(73) = 72[/tex]

    So n=72 works... But Dick commented about numbers less then 72 so I figured it couldn't be that... I took the gcd(72,24) got 24, gcd(72,40) got 8, gcd(72,48) got 24. Then I took the gcd(24,8) and got 8, so it's every multiple of 8 -- and that worked but not really not sure maybe someone else can make sense of it...
     
  5. Jul 13, 2007 #4

    Dick

    User Avatar
    Science Advisor
    Homework Helper

    Once you have 10^8(mod 73)=1 the rest is pretty much a foregone conclusion.
     
Share this great discussion with others via Reddit, Google+, Twitter, or Facebook