2

Definition of prime is that a natural number $n > 1$ is prime if the only natural numbers $m$ with $m|n$ are $m = 1$ and $m = n$.

I'm guessing this means that the prime numbers can only be divided between $1$ and the prime number itself. But how can I properly use this definition to prove?

Proposition: If $n > 1$ is a natural number, then there is a prime number $p$ such that $p|n$

Proof:

$n = pq$ for some integer $q$

Case 1: If $p = 1$, then $n = (1)*q$

Case 2: If $p = n$, then $n = (n)*q$

Therefore, there is a prime number $p$ such that $p|n$

Would something like this work?

Krijn
  • 1,945
  • 16
  • 32
dendritic
  • 315
  • How are you finding $p$? Is it just something being pulled from thin air? – JB King Sep 19 '15 at 23:10
  • your proof isnot correct http://math.stackexchange.com/questions/934660/proof-that-every-number-has-at-least-one-prime-factor – R.N Sep 19 '15 at 23:12
  • you may want to look into the fundamental theorem of arithmetic, an easy to prove theorem which gives you your proof and more – Thomas Pouget Sep 25 '15 at 21:50

2 Answers2

5

If $n$ is prime then it divides itself and finished. Let $S=\{a> 1: a\vert n\}$ be a set, it has minimal element, call it $d$. Now $d$ is prime else there is $k$ such that $k\vert d$, but since $d\vert n$ then $k\vert n$ contradicts minimality.

janmarqz
  • 10,538
R.N
  • 4,318
2

Outline: Let $n\gt 1$, and let $q$ be the smallest integer greater than $1$ that divides $n$. Note that $q$ could be $n$.

Show that $q$ is prime by reaching a contradiction from the assumption it is not prime.

André Nicolas
  • 507,029