Interesting number theory question

[lugita15]

Homework Statement

For what natural numbers n is (10^n)-1 divisible by 73?

Homework Equations

N/A

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?

 

[Dick]

How about 24,40,48 etc?

 

[Feldoh]

Not sure how I got there but I think I have the right answer... thought it could be trivialized by Fermat's Little Theorem.

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

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...

 

[Dick]

Once you have 10^8(mod 73)=1 the rest is pretty much a foregone conclusion.