- #1

Math100

- 791

- 220

- Homework Statement
- If ## gcd(a, 133)=gcd(b, 133)=1 ##, show that ## 133\mid (a^{18}-b^{18}) ##.

- Relevant Equations
- None.

Proof:

Suppose ## gcd(a, 133)=gcd(b, 133)=1 ##.

Then ## 133=7\cdot 19 ##.

Applying the Fermat's theorem produces:

## a^{6}\equiv 1\pmod {7}, b^{6}\equiv 1\pmod {7} ##,

## a^{18}\equiv 1\pmod {19} ## and ## b^{18}\equiv 1\pmod {19} ##.

Observe that

\begin{align*}

&a^{6}\equiv 1\pmod {7}\implies (a^{6})^{3}\equiv 1^{3}\pmod {7}\implies a^{18}\equiv 1\pmod {7}\\

&b^{6}\equiv 1\pmod {7}\implies (b^{6})^{3}\equiv 1^{3}\pmod {7}\implies b^{18}\equiv 1\pmod {7}.\\

\end{align*}

This means ## a^{18}-b^{18}\equiv (1-1)\pmod {7}\equiv 0\pmod {7} ## and ## a^{18}-b^{18}\equiv (1-1)\pmod {19}\equiv 0\pmod {19} ##.

Thus, ## 7\mid (a^{18}-b^{18}) ## and ## 19\mid (a^{18}-b^{18}) ##.

Since ## gcd(7, 19)=1 ##, it follows that ## (7\cdot 19)\mid (a^{18}-b^{18})\implies 133\mid (a^{18}-b^{18}) ##.

Suppose ## gcd(a, 133)=gcd(b, 133)=1 ##.

Then ## 133=7\cdot 19 ##.

Applying the Fermat's theorem produces:

## a^{6}\equiv 1\pmod {7}, b^{6}\equiv 1\pmod {7} ##,

## a^{18}\equiv 1\pmod {19} ## and ## b^{18}\equiv 1\pmod {19} ##.

Observe that

\begin{align*}

&a^{6}\equiv 1\pmod {7}\implies (a^{6})^{3}\equiv 1^{3}\pmod {7}\implies a^{18}\equiv 1\pmod {7}\\

&b^{6}\equiv 1\pmod {7}\implies (b^{6})^{3}\equiv 1^{3}\pmod {7}\implies b^{18}\equiv 1\pmod {7}.\\

\end{align*}

This means ## a^{18}-b^{18}\equiv (1-1)\pmod {7}\equiv 0\pmod {7} ## and ## a^{18}-b^{18}\equiv (1-1)\pmod {19}\equiv 0\pmod {19} ##.

Thus, ## 7\mid (a^{18}-b^{18}) ## and ## 19\mid (a^{18}-b^{18}) ##.

Since ## gcd(7, 19)=1 ##, it follows that ## (7\cdot 19)\mid (a^{18}-b^{18})\implies 133\mid (a^{18}-b^{18}) ##.