Results 1 to 3 of 3

Math Help - Proof of primes.

  1. #1
    Super Member Showcase_22's Avatar
    Joined
    Sep 2006
    From
    The raggedy edge.
    Posts
    782

    Proof of primes.

    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!
    Follow Math Help Forum on Facebook and Google+

  2. #2
    Member
    Joined
    Jul 2008
    Posts
    81
    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.
    Follow Math Help Forum on Facebook and Google+

  3. #3
    Moo
    Moo is offline
    A Cute Angle Moo's Avatar
    Joined
    Mar 2008
    From
    P(I'm here)=1/3, P(I'm there)=t+1/3
    Posts
    5,618
    Thanks
    6
    Quote Originally Posted by Showcase_22 View Post
    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.
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. Odd Primes Proof (Should be simple)
    Posted in the Number Theory Forum
    Replies: 11
    Last Post: May 14th 2010, 11:42 AM
  2. Proof of primes
    Posted in the Number Theory Forum
    Replies: 1
    Last Post: March 10th 2010, 08:35 PM
  3. Mod proof with primes
    Posted in the Number Theory Forum
    Replies: 2
    Last Post: February 1st 2010, 06:32 PM
  4. proof of inifinite primes
    Posted in the Number Theory Forum
    Replies: 6
    Last Post: December 13th 2008, 01:10 AM
  5. Primes proof
    Posted in the Number Theory Forum
    Replies: 1
    Last Post: December 21st 2005, 06:13 AM

Search Tags


/mathhelpforum @mathhelpforum