This is from the Number Theory Book by Joseph Silverman.
This is the introduction before he goes on to Euler's Phi Function.
In the previous chapter we proved Fermat's Little Theorem: If p is a prime and p doesn't divide a, then $a^{p-l} \equiv 1 \pmod p$. This formula is certainly not true if we replace p by a composite number. For example, $5^5 \equiv 5 \pmod 6$ and $2^8 \equiv 4 \pmod 9$. So we ask whether there is some power, depending on the modulus m, such that $a^{???} \equiv 1 \pmod m$ . Our first observation is that this is impossible if gcd(a,m) > 1. To see why, suppose that $a^{k} \equiv 1 \pmod m$. Then $a^{k} = 1 + my$ for some integer y, so gcd(a,m) divides $a^{k} -my = 1$. In other words, if some power of a is congruent to 1 modulo m, then we must have gcd(a,m) = 1.
I am unable to understand the last 2 lines here
- Then $a^{k} = 1 + my$ for some integer y, so gcd(a,m) divides $a^{k} - my = 1$.
What does the above line mean? $a^{k} - my = 1$ is an equation. How can gcd(a,m) divide an equation?
Then I don't understand how the next line also comes about
- In other words, if some power of a is congruent to 1 modulo m, then we must have gcd(a,m) = 1.
Can someone please help?
If $c \equiv 1 \pmod{b}$, then what this mean is $c-1 \equiv 0 \pmod{b}$ or $c-1$ is a multiple of $b$.
We have $a^k \equiv 1 \pmod{m}$, hence $a^k-1$ is a multiple of $m$, hence we can find an integer $y$ such that $a^k-1 = my$.
Rearranging the equation, $$a^k - my =1$$
For $k \ge 1$, by the definition of common divisor, $\gcd(a, m)$ must divide $a$ and it must also divides $m$, hence it must divide $a^k-my$ which is equal to $1$.
$\gcd(a,m)$ divides $1$. The only positive integer that divides $1$ is $1$.
Hence $\gcd(a,m)$ must be $1$.