# Homework Help: Interesting number theory question

1. Jul 13, 2007

### lugita15

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. Jul 13, 2007

### Dick

3. Jul 13, 2007

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

4. Jul 13, 2007

### Dick

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