Proof of primes.

**Showcase_22** · April 25th 2009, 01:09 PM

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!

**siclar** · April 25th 2009, 04:05 PM

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.

**Moo** · April 26th 2009, 12:12 AM

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$

$\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

$\sqrt{\frac{n}{p_i^2}}=\frac{\sqrt{n}}{p_i}{\color {red}=}\sqrt{\frac{n}{p_i}}$

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

siclar's proof is the correct one ^^

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

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.

Thread: Proof of primes.

LinkBack

Thread Tools

Display

Proof of primes.

Similar Math Help Forum Discussions

Odd Primes Proof (Should be simple)

Proof of primes

Mod proof with primes

proof of inifinite primes

Primes proof

Search Tags