- #1

Math100

- 771

- 219

- Homework Statement
- If ## gcd(a, 42)=1 ##, show that ## 168=3\cdot 7\cdot 8 ## divides ## a^{6}-1 ##.

- Relevant Equations
- None.

Proof:

Suppose ## gcd(a, 42)=1 ##.

Then ## 42=2\cdot 3\cdot 7 ## and ## gcd(a, 2)=gcd(a, 3)=gcd(a, 7)=1 ##.

Applying the Fermat's theorem produces:

## a\equiv 1\pmod {2}, a^{2}\equiv 1\pmod {3} ## and ## a^{6}\equiv 1\pmod {7} ##.

This means ## a^{6}=(a^{2})^{3}\equiv 1\pmod {3} ##.

Observe that ## a^{6}-1=(a^{3}-1)(a^{3}+1)=(a-1)(a+1)(a^{2}+a+1)(a^{2}-a+1) ##.

Since ## a ## is odd, it follows that ## a>0\implies a\geq 3 ##.

Now we have ## a^{2}\equiv 1\pmod {8}\implies (a^{2})^{3}\equiv 1^{3}\pmod {8}\implies a^{6}\equiv 1\pmod {8} ##.

Thus, ## 168\mid (a^{6}-1) ## because ## 3, 7, 8 ## are relatively prime to each other.

Therefore, if ## gcd(a, 42)=1 ##, then ## 168=3\cdot 7\cdot 8 ## divides ## a^{6}-1 ##.

Suppose ## gcd(a, 42)=1 ##.

Then ## 42=2\cdot 3\cdot 7 ## and ## gcd(a, 2)=gcd(a, 3)=gcd(a, 7)=1 ##.

Applying the Fermat's theorem produces:

## a\equiv 1\pmod {2}, a^{2}\equiv 1\pmod {3} ## and ## a^{6}\equiv 1\pmod {7} ##.

This means ## a^{6}=(a^{2})^{3}\equiv 1\pmod {3} ##.

Observe that ## a^{6}-1=(a^{3}-1)(a^{3}+1)=(a-1)(a+1)(a^{2}+a+1)(a^{2}-a+1) ##.

Since ## a ## is odd, it follows that ## a>0\implies a\geq 3 ##.

Now we have ## a^{2}\equiv 1\pmod {8}\implies (a^{2})^{3}\equiv 1^{3}\pmod {8}\implies a^{6}\equiv 1\pmod {8} ##.

Thus, ## 168\mid (a^{6}-1) ## because ## 3, 7, 8 ## are relatively prime to each other.

Therefore, if ## gcd(a, 42)=1 ##, then ## 168=3\cdot 7\cdot 8 ## divides ## a^{6}-1 ##.