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