Thread: 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!!!

Originally Posted by fruitbodywash

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 a product of three or more three prime numbers then each one must be . Because otherwise we get that .

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 where the factors are non-trivial then . 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,

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.