(adsbygoogle = window.adsbygoogle || []).push({}); 1. The problem statement, all variables and given/known data

prove that p is prime iff for any integer "a" either (a,p)=1 or p divides a

(where (a,p) denotes the gcd of a and p)

2. Relevant equations

(a,b)= the greatest common factor of a and b

3. The attempt at a solution

I had no trouble with proving the forward direction of the statement. But for the backward direction, here is what I have:

for any integer "a", let either (a,p)=1 or p divide a

Now assume that p is not prime.

The following must hold true:

either (6,4)=1 or 4 divides 6

Since both of these statements are false, this is a contradiction.

Therefore p must be prime.

Q.E.D.

It seems okay to me to use an example at this point to arrive at the contradiction. Is this a legitimate way to prove the theorem?

**Physics Forums | Science Articles, Homework Help, Discussion**

Join Physics Forums Today!

The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

# Homework Help: Proof about primes and gcd

**Physics Forums | Science Articles, Homework Help, Discussion**