How are the Terms $Congruence$ and $Relatively$ $Prime$ Related?

Question

I saw this line in a textbook, but I can't understand how they inferred that $\gcd(a,p) = 1$.

"If $p$ is a prime number and $a \not\equiv0 \pmod{p}$, then $\gcd(a,p) = 1$."

Answer 1

If $p$ is a prime number, and $a$ is not a multiple of $p$, then $a$ and $p$ are coprime. $a\equiv 0 \mod p$ implies that $a$ is a multiple of $p$.

Answer 2

If $a$ isn't a multiple of $p$, then $a$ isn't divisible by $p$. Nor is $a$ divisible by any factor of $p$: there aren't any.

But, of course, $p$ can't be divisible by $a$, either, since $p$ is prime.

Thus they're relatively prime.

Notice if you take a non-prime, this fails. For instance, $9$ isn't a multiple of $6$; but $9$ and $6$ aren't relatively prime. That's because $6$ isn't prime, and shares a factor, $3$, with $9$.

Answer 3

They are related in this case, by the fact that $a$ doesn't have $p$ as a factor, and $p$ can't have $a$ as a factor unless $a$ is 1. This case is used, repeatedly in Fermat's little theorem, Euler's totient theorem, and the simpler cases of Chinese Remainder Theorem.

Answer 4

Let $p$ be a prime number and $a \not\equiv0 \pmod{p}$.

This means that $p \nmid a$.

Now, if $p$ were composite, it is possible that $p$ and $a$ could share a nontrivial common factor other than $p$; however, as $p$ is prime, the only nontrivial factor that they could share is $p$. But, as $p \nmid a$, it follows that

$$\gcd(a,p) = 1.$$

Answer 5

Bear in mind that $k \equiv 0 \pmod n$ is true if and only if $n$ divides into $k$.[1]

Also bear in mind that a prime number, $p$ has no factors other than $1$ and itself.

Thirdly remember $\gcd(a,p)$ means, literally, the greatest divisor $a$ and $p$ have in common.

...........

So... the only divisor that $p$ has is $1$ and itself. So the only possible divisors that $a$ and $p$ could possibly have in common are $1$ or $p$.

If $a \equiv 0 \pmod p$ then $p$ divides into $a$. And so they have $p$ as a common factor. The only other factor the have in common is $1$ (every integer has $1$ as a factor). So the greatest common factor they have in common is $p$.

If $a\not\equiv 0\pmod p$ then $p$ does not divide into $a$. And so they do not have $p$ as common factor. So the only factor they have in common is $1$. So the greatest common factor between them is $1$.[2]

That's it.

======

[1] Perhaps $n$ divides $k$ iff and only if $k\equiv 0\pmod n$ is the only one of these three ideas that isn't explicitly part of its definition.

But $k \equiv m \pmod n$ means that $n$ divides $k-m$ so $k\equiv 0\pmod n$ means $n$ divides $k-0=k$.

So it is implicitly part of the definition.

Or perhaps it is more natural for you to think of $k \equiv m \pmod n$ as either "$k$ and $m$ have the same remainder" or $k = m + dn$ for some integer $n$. But these definitions mean the exact same thing.

$0$ has $0$ remainder when divided by anything. So $k \equiv 0 \pmod n$ means $k$ has $0$ remainder when divided by $n$..... which means $n$ divides into $k$.

Or if $k = 0 + dn=dn$ for some integer $d$.... well, that's the very definition of $n$ dividing into $k$.

======

[2] It goes the other way too. If $\gcd(a,p)=1$ then $a \not \equiv 0\pmod p$.

The only factors $a$ and $p$ could have in common would be $p$ or $1$.

And if they have $p$ in common then.... $p$ is a factor of $a$ and $a \equiv 0 \pmod p$.

And if they don't have $p$ in common then $p$ is not a factor of $a$ and $a \not \equiv 0 \pmod p$.