# Suppose two integers $a,N$, where N is prime, is there a difference between requiring $gcd(a,N)=1$ and $N \not\mid \!\!\;a$?

This is probably painfully obvious but I wanted to confirm if there's any difference between requiring that the $$gcd(a,N)=1$$ or $$N \not\mid \!\!\;a$$ if N is prime? That is, could you use either requirement and achieve the same result?

• Can you prove it? – Jihoon Kang Jul 17 at 17:08
• only difference is the time you need to type this in $\LaTeX$ ;) – Luis Felipe Jul 17 at 17:15

There is no difference, each requirement implies the other. If $$\gcd(a,N)=1$$ then obviously $$N$$ can't divide $$a$$ because otherwise $$N$$ would be a common divisor of $$a,N$$ which is bigger than $$1$$.
Now suppose $$N$$ does not divide $$a$$. Let $$d$$ be a positive common divisor of $$a,N$$. Since $$N$$ is prime we know $$d=N$$ or $$d=1$$. But $$N$$ does not divide $$a$$, hence $$d=1$$. So $$1$$ is the only positive common divisor of $$a,N$$, hence it is the $$\gcd$$.
• What is a prime number? $N$ is prime if its positive divisors are $1$ and $N$. – Mark Jul 17 at 17:48
Negate:  prime $$\, \color{#c00}{p\mid a} \iff p\mid a,p\iff \overbrace{p\mid (a,p)\iff \color{#c00}{(a,p)\neq 1}}^{\textstyle \hphantom{p\mid (a,p)} \ {\Longleftarrow\ \ (a,p)\mid p}}$$