- #1

Math100

- 779

- 220

- Homework Statement
- If ## gcd(a, 30)=1 ##, show that ## 60 ## divides ## a^{4}+59 ##.

- Relevant Equations
- None.

Proof:

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

Then ## 30=2\cdot 3\cdot 5 ## and ## gcd(a, 2)=gcd(a, 3)=gcd(a, 5)=1 ##.

Applying the Fermat's theorem produces:

## a\equiv 1\pmod {2}, a^{2}\equiv 1\pmod {3} ## and ## a^{4}\equiv 1\pmod {5} ##.

This means ## gcd(a, 4)=gcd(a, 2^{2})=1 ##.

Observe that

\begin{align*}

&a\equiv 1\pmod {2}\implies a^{2}\equiv 1\pmod {2}\\

&a^{2}\equiv 1\pmod {3}\implies a^{4}\equiv 1\pmod {3}.\\

\end{align*}

Now we have ## 2\mid (a^{2}-1)\implies a^{2}\equiv (1-2)\pmod {2}\equiv -1\pmod {2} ##,

so ## 4\mid (a^{2}+1)(a^{2}-1)\implies 4\mid (a^{4}-1) ##.

Since ## 60=3\cdot 4\cdot 5 ## and ## 3, 4, 5 ## are relatively prime to each other,

it follows that ## 60\mid (a^{4}-1) ##.

Thus ## a^{4}\equiv 1\pmod {60}\equiv (1-60)\pmod {60}\equiv -59\pmod {60} ##.

Therefore, if ## gcd(a, 30)=1 ##, then ## 60 ## divides ## a^{4}+59 ##.

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

Then ## 30=2\cdot 3\cdot 5 ## and ## gcd(a, 2)=gcd(a, 3)=gcd(a, 5)=1 ##.

Applying the Fermat's theorem produces:

## a\equiv 1\pmod {2}, a^{2}\equiv 1\pmod {3} ## and ## a^{4}\equiv 1\pmod {5} ##.

This means ## gcd(a, 4)=gcd(a, 2^{2})=1 ##.

Observe that

\begin{align*}

&a\equiv 1\pmod {2}\implies a^{2}\equiv 1\pmod {2}\\

&a^{2}\equiv 1\pmod {3}\implies a^{4}\equiv 1\pmod {3}.\\

\end{align*}

Now we have ## 2\mid (a^{2}-1)\implies a^{2}\equiv (1-2)\pmod {2}\equiv -1\pmod {2} ##,

so ## 4\mid (a^{2}+1)(a^{2}-1)\implies 4\mid (a^{4}-1) ##.

Since ## 60=3\cdot 4\cdot 5 ## and ## 3, 4, 5 ## are relatively prime to each other,

it follows that ## 60\mid (a^{4}-1) ##.

Thus ## a^{4}\equiv 1\pmod {60}\equiv (1-60)\pmod {60}\equiv -59\pmod {60} ##.

Therefore, if ## gcd(a, 30)=1 ##, then ## 60 ## divides ## a^{4}+59 ##.