# Homework Help: Number theory: Modulus and Divisibility problem

1. May 12, 2013

### Tim67

1. The problem statement, all variables and given/known data

Prove that if gcd(a, 133) = 1, then 133 divides (a^18 - 1).

3. The attempt at a solution

This is an old homework question as I'm going over the homeworks to review for the test, but can't seem to get this right. Which is annoying because I remember I did it fine back in the course when this homework was actually due.

So, I know gcd(a, 133) = 1 implies 133 divides a^phi(133) -1 = a^108 -1. So I assume I'd want to factor that out so that I get a product of polynomials, one of the form (a^18 - 1), and show that the other polynomial factors aren't divisible by 133 by appealing to their modulus form. But that doesn't seem to be working out.

2. May 12, 2013

### Staff: Mentor

Can you show where exactly you run into problems? The approach looks good, I think.

3. May 13, 2013

### Tim67

It just doesn't factor easily, and generally in this class the problems have been computationally simple once you know the right approach to take, so that's making me think it can't be right. I mean, I'd want to factor it so I get a product of (a^x -1)(a^y + 1) .... (a^z +1) etc so that I can easily show that none of the other factors are divisible, but it doesn't seem like it'll break up like that:

I can get (a^108 - 1) = (a^54 -1)(a^54 +1) = (a^27 - 1)(a^27+1)(a^54 + 1) etc. I think I need to factor it into forms like that to get a product of factors only of the form I can convert into modulus representations. But it doesn't seem I can do that.

4. May 13, 2013

### Staff: Mentor

$$a^{108-1} = (a^{18})^6-1 = (a^{18}-1)(...)$$

I think you can show that a^18=1 mod 7 and/or a^18=1 mod 19 is the only way to solve this (so the other expression cannot be 0 mod 133).