Show that a positive integer $n \in \mathbb{N}$ is prime if and only if $\gcd(n,m)=1$ for all $0<n<m$.

Question

Show that a positive integer $n \in \mathbb{N}$ is prime if and only if $\gcd(n,m)=1$ for all $0<m<n$.

I know that I can write $n=km+r$ for some $k,r \in \mathbb{Z}$ since $n>m$

and also that $1=an+bm$. for some $a,b \in \mathbb{Z}$

Further, I know that $n>1$ if I'm to show $n$ is prime.

I'm not sure how I would go about showing this in both directions though.

Answer 1

Hint: If $d$ divides $n$, then $gcd(d,n)=d$.

Answer 2

What you've written on the right of the iff. is the definition of a prime number. You have just stated it using more concise notation.

According to the wolfram page for Prime Number,

A prime number (or prime integer, often simply called a "prime" for short) is a positive integer p>1 that has no positive integer divisors other than 1 and p itself.

Answer 3

This should be trivial.

If n is prime it has no factors but 1 and n. So gcd (n,m) can only equal 1 or n. If gcd(n,m) = n then that means n|m. So m $\ge$ n. So if m < n then gcd (n,m)=1.

That's one way.

If gcd (n,m)=1 for all m < n, then no number less than n divides n (other than 1). As no number larger n divides n, n has no divisors except itself and 1. So n is prime.

That's the other way.