# primality testing - ugh - HELP

• Sep 16th 2007, 08:56 PM
fruitbodywash
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!!!
• Sep 16th 2007, 09:26 PM
ThePerfectHacker
Quote:

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 $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$.
Quote:

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.

Quote:

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} )$

Quote:

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.