3

I've been having serious trouble with this problem,

The first direction->

Proving x is prime if for every integer y, either gcd(x,y)=1 or x|y doesn't seem too difficult.

We know that if gcd(x,y)=1 then they are coprime.. but what does the fact that x|y tell us that would allow us to conclude that x is prime?

And the other direction..

Prove either gcd(x,y)=1 or x|y if x is prime. Seems easier, I haven't gotten around to finishing it, but I assume I would use the definition of a prime number to prove it?

I.e. x is only divisible by 1 or x... Am I on the right track for this proof?..

Yiorgos S. Smyrlis
  • 83,933
user122661
  • 983

2 Answers2

1

Suppose $x$ is not prime. Then by definition there exists a $y$ such that $y|x$ and $y<x$. So, gcd$(x,y)=y \neq 1$.

For the other direction:

Suppose $x$ is prime. Let $y$ be another integer. Now, gcd$(x,y)$ divides $x$, and since $x$ is prime, gcd$(x,y)=x$ or $1$. If gcd$(x,y)=x$ then by definition of gcd, $x|y$. So, for every integer $y$ either gcd$(x,y)=1$ or $x|y.$

voldemort
  • 13,182
  • Considering you're using mostly properties of prime numbers, would this proof be adequate for marking or should more detail/explanation be added to justify the steps? – user122661 Jan 21 '14 at 18:48
  • @user122661: Do you mean proof of the other direction? I can add more details if you want. Proof of the direction that I showed is adequate. – voldemort Jan 21 '14 at 20:17
  • Yes, for the other direction I mean.. simple reasoning as opposed to mathematical calculations can be used, correct? – user122661 Jan 21 '14 at 21:07
  • @user122661: I edited my answer to include a solution for the other direction. – voldemort Jan 21 '14 at 21:12
1

$\ p\mid y\iff (p,y)\ge p\,$ so we want to show: $ $ prime $\,p \!\iff\! (p,y) \le 1\ $ or $\,(p,y) \ge p\,$ for all $y.\,$ Its negation is: $ $ composite $\,p\!\iff\! 1 < (p,y) < p\,$ for some $y.\,$ It's true, let $\,y\,$ be a proper factor of $\,p$.

Bill Dubuque
  • 272,048