Results 1 to 2 of 2

Math Help - primality testing - ugh - HELP

  1. #1
    Newbie
    Joined
    Sep 2007
    Posts
    14

    Unhappy primality testing - ugh - HELP

    Alright, we were told to do all the problems in the section on primality testing. I did alright on the first few... i think... but I am unable to figure out or even begin on more than half of them. I'm going crazy!!! I don't understand the explination that is given in the section, or i don't understand how to use what I do understand. So, I'm going to give a few of the problems, and if anyone can give a detailed explination (in the simplest terms) on how to do these.... I would be forever grateful!

    the first one, i think I solved it, but... I'm a little iffy on it:

    let n be greater than 1, if n has no prime factor less than or equal to the cubed route of n, prove that n is either a prime number, or is a product of two primes....
    ~~~ what I found, was if n is greater than 8, it will always have a prime number that is less than or equal too the cubed route of n, even if n is prime or a product of two prime numbers.... but, if n is less than 8 (and greater than 1), than the cubed route of n is greater than 1, but less than 2. So.... what am I supose to prove?


    ok, another one, I don't know how to really prove it,

    Let p>1, if (2^p) - 1 is prime, prove that p is prime. [Hint: Prove the contrapositive: If p is composite, so is (2^p) - 1. Note: The convers is false]

    I'm not sure I know what composite means, and even if I did, I'm not sure I would know how to begin. I know that the converse is false, because if p = 11, then (2^p) - 1 is not prime.... but.... *groans* I don't know how to prove what its asking for.... even with the hint.

    and next (I told you i was having a lot of trouble):

    let a, b be nonnegative integers not both 1. If k is odd and k >= (greater than or equal) 3, prove that a^k + b^k is not prime.

    I didn't get very far on this one... not really sure I know how to start it...

    and this one.... I tried, but, I'm just a weee bit confused, I've tried putting in values, and testing it, but.... I'ts not really working...

    if n is a positive integer of the form 4k +3, prove that n has a prime factor of the form 4k + 3.

    I've tried rearranging the formulas, for example, since n = 4k + 3, and p|n, then p = 4j + 3... next... since p|n, then n = px, then 4k + 3 = (4j +3)x and thats about where I get hung up....

    *groans* and this list goes on, and on, and ooooonn! I haven't even put half of the problems that are driving me crazy, and I'm suppose to understand this by today!!!
    Follow Math Help Forum on Facebook and Google+

  2. #2
    Global Moderator

    Joined
    Nov 2005
    From
    New York City
    Posts
    10,616
    Thanks
    10
    Quote Originally Posted by fruitbodywash View Post
    let n be greater than 1, if n has no prime factor less than or equal to the cubed route of n, prove that n is either a prime number, or is a product of two primes....
    If n=pqr a product of three or more three prime numbers then each one must be \leq \sqrt[3]{n}. Because otherwise we get that n>n.
    Let p>1, if (2^p) - 1 is prime, prove that p is prime. [Hint: Prove the contrapositive: If p is composite, so is (2^p) - 1. Note: The convers is false]
    If p=ab where the factors are non-trivial then 2^{ab} - 1 = (2^a)^b - 1 = (2^a-1)((2^a)^{b-1}+...+2^a+1). Which cannot be prime.

    let a, b be nonnegative integers not both 1. If k is odd and k >= (greater than or equal) 3, prove that a^k + b^k is not prime.
    Factorize,
    a^k+b^k = (a+b)(a^{k-1}-a^{k-2}b+a^{k-3}b^2-...\pm ab^{k-2}\mp b^{k-1} )

    if n is a positive integer of the form 4k +3, prove that n has a prime factor of the form 4k + 3.
    If each prime factor was of the form 4k+1 then n would too.
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. The fastest way to test primality ?
    Posted in the Number Theory Forum
    Replies: 4
    Last Post: December 9th 2011, 10:00 AM
  2. Simple primality testing algorithm
    Posted in the Discrete Math Forum
    Replies: 1
    Last Post: April 27th 2011, 09:33 AM
  3. Wilson's Primality Test ... what ?
    Posted in the Number Theory Forum
    Replies: 3
    Last Post: June 9th 2010, 07:44 AM
  4. Simultaneous integer primality testing
    Posted in the Number Theory Forum
    Replies: 0
    Last Post: April 12th 2009, 07:40 PM
  5. [HELP]Relative Primality in the Following Algorithm
    Posted in the Number Theory Forum
    Replies: 0
    Last Post: October 28th 2008, 07:37 AM

Search Tags


/mathhelpforum @mathhelpforum