Number theory: Modulus and Divisibility problem

[Tim67]

Homework Statement

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

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.

 

[mfb]

But that doesn't seem to be working out.

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

 

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

 

[mfb]

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