# Proof of primes.

• Apr 25th 2009, 01:09 PM
Showcase_22
Proof of primes.
Quote:

Prove that if $p_1,...,p_n$ are the primes up to $\sqrt{n}$, and if each $p_i$ does not divide n, then n is prime.
My proof so far:

$\frac{\sqrt{n}}{p_i}=ap_i+r$ where $a,r \in \mathbb{Z}-\{0\} \ , \ a,r \neq 0$.

$\frac{\sqrt{n}}{p_i}=ap_i+r \Rightarrow \ \sqrt{\frac{n}{p_i}}=ap_i+r \Rightarrow \ \frac{n}{p_i}=(ap_i+r)^2=a^2p_i^2+2arp_i+r^2$

From here it's easy to see that my working can be rearranged to get $n=p_i(a^2p_i^2+2arp_i+r^2)$ showing that n is divisible by $p_i$.

This is annoying since I want to show that n is prime!
• Apr 25th 2009, 04:05 PM
siclar
You are overcomplicating the question! Assume the primes less than the squareroot of n do not divide n, and n is not prime. Then there is some prime p dividing n. By assumption, p must be larger than the square root of n. But n=pq for some integer q, and clearly q is less than the square root of n. Either q is divisible by a prime less than the square root of n, or q=1. In the first case we contradict our assumption since x divides q implies x divides n. In the second case, p=n is prime, which again contradicts our assumption.
• Apr 26th 2009, 12:12 AM
Moo
Quote:

Originally Posted by Showcase_22
My proof so far:

$\frac{\sqrt{n}}{p_i}=ap_i+r$ where $a,r \in \mathbb{Z}-\{0\} \ , \ a,r \neq 0$.

What was that supposed to do ??? Writing the assumption "none of the p_i < sqrt(n)" divide n ?
It doesn't make sense, since $\sqrt{n}$ is not necessarily an integer ! Moreover, what's the point dividing sqrt(n) by p_i ?

If you wanted to do that, you should've written : $n=ap_i+r$

Quote:

$\frac{\sqrt{n}}{p_i}=ap_i+r \Rightarrow \ \sqrt{\frac{n}{p_i}}=ap_i+r \Rightarrow \ \frac{n}{p_i}=(ap_i+r)^2=a^2p_i^2+2arp_i+r^2$
I hope you were just tired (Surprised)
$\sqrt{\frac{n}{p_i^2}}=\frac{\sqrt{n}}{p_i}{\color {red}=}\sqrt{\frac{n}{p_i}}$

Quote:

From here it's easy to see that my working can be rearranged to get $n=p_i(a^2p_i^2+2arp_i+r^2)$ showing that n is divisible by $p_i$.

This is annoying since I want to show that n is prime!
Well, see above :D

siclar's proof is the correct one ^^
Quote:

But n=pq for some integer q, and clearly q is less than the square root of n.
in order to prove that, suppose that $q>\sqrt{n}$
we would then have pq>n, which is a contradiction

Quote:

Either q is divisible by a prime (logically) less than the square root of n, or q=1. In the first case we contradict our assumption since x divides q implies x divides n. In the second case, p=n is prime, which again contradicts our assumption.