Results 1 to 5 of 5
Like Tree1Thanks
  • 1 Post By HallsofIvy

Math Help - Number Theory

  1. #1
    mlg
    mlg is offline
    Junior Member
    Joined
    Oct 2013
    From
    Ireland
    Posts
    64

    Number Theory

    I need help with this problem please.
    Why is it sufficient
    to test that p does not have any divisors
    ≤ square root of p, to prove that the number p is prime or not.
    Follow Math Help Forum on Facebook and Google+

  2. #2
    MHF Contributor

    Joined
    Apr 2005
    Posts
    16,449
    Thanks
    1864

    Re: Number Theory

    If x is a divisor of p then there exist an integer, y, such that p= xy. If x is larger than the square root f p, what must be true of y?
    Thanks from topsquark
    Follow Math Help Forum on Facebook and Google+

  3. #3
    mlg
    mlg is offline
    Junior Member
    Joined
    Oct 2013
    From
    Ireland
    Posts
    64

    Re: Number Theory

    Thank you for your time and effort.
    This type of maths is new to me so it will take me some time to work it out.
    Follow Math Help Forum on Facebook and Google+

  4. #4
    Super Member
    Joined
    Dec 2012
    From
    Athens, OH, USA
    Posts
    713
    Thanks
    299

    Re: Number Theory

    Maybe this will help.
    Suppose p is an integer greater than 1 and p is not a prime. Let q be the smallest prime divisor of p. (You need to know that any integer greater than 1 is either a prime or a product of at least two primes.). Say $p = qr,\,q\leq r$ and so $q^2\leq qr=p$. That is, $q\leq\sqrt p$

    So if you test all primes q with $q\leq \sqrt p$ and none of these divide p, then p must be prime: if p were not prime the above paragraph shows there is a prime q with $q\leq \sqrt p$ and q is a divisor of p.
    Follow Math Help Forum on Facebook and Google+

  5. #5
    mlg
    mlg is offline
    Junior Member
    Joined
    Oct 2013
    From
    Ireland
    Posts
    64

    Re: Number Theory

    Thank you for your time and effort and your excellent explanation.
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. Number theory
    Posted in the New Users Forum
    Replies: 4
    Last Post: June 2nd 2012, 11:59 PM
  2. Using group theory to prove results in number theory
    Posted in the Math Philosophy Forum
    Replies: 6
    Last Post: May 12th 2012, 02:34 AM
  3. Textbooks on Galois Theory and Algebraic Number Theory
    Posted in the Advanced Algebra Forum
    Replies: 3
    Last Post: July 8th 2011, 07:09 PM
  4. Replies: 2
    Last Post: December 18th 2008, 06:28 PM
  5. Number theory, prime number
    Posted in the Number Theory Forum
    Replies: 1
    Last Post: September 17th 2006, 09:11 PM

Search Tags


/mathhelpforum @mathhelpforum