Prime numbers

how do you prove that number is not Prime?

the example in my book says prove that 2 to the power of 66 is not prime and then says the keys lies in this simple algebra x squared-1=(x-1)(x+1) it says to use that to write a proof that the number is not prime so what am supposed to do with that equation?

Reply 1

generalebriety

16

I think you mean you're meant to prove that

2^{66} - 1

isn't prime?

Let x = 2^33. Show that your number has at least one factor which isn't 1 or 2^66 - 1 itself, and you've shown it's not prime.

Reply 2

alexmahone

lol, 2^66 is even, for god's sake!

Reply 3

nota bene

15

alexmahone

lol, 2^66 is even, for god's sake!

And that proves? :s-smilie:

Reply 4

alexmahone

nota bene

And that proves? :s-smilie:

that it isn't prime.

Reply 5

BJack

19

alexmahone

that it isn't prime.

But 2 is even. >.>

Reply 6

alexmahone

BJack

But 2 is even. :s-smilie:

But 2^66 isn't 2! :cool:

Reply 7

nota bene

15

An even number (apart from 2) will always be divisible by 2 (and 1 and itself) and thus not prime, but your argument seemed to be that an even number can't be prime...

Reply 8

Dadeyemi

13

andrewk

how do you prove that number is not Prime?

the example in my book says prove that 2 to the power of 66 is not prime and then says the keys lies in this simple algebra x squared-1=(x-1)(x+1) it says to use that to write a proof that the number is not prime so what am supposed to do with that equation?

what is the definition of a prime? no factors except itself and 1. Just show it has factors other than itself and 1 that can be shown by factorizing it as the difference of two squares.

Reply 9

boy

But 66 is even so 2^66 is even. But I don't think that's the proof they want

Reply 10

alexmahone

Actually, you can use Fermat's little theorem to show that

2^{66}=1 (mod\ 67)

So,

2^{66}-1

is divisible by 67

Reply 11

Horizontal 8

10

just show it has any factor besides 2^66 and 1 e.g. 2,4, etc
EDIT:Oh so the question actually means show that 2^66 -1 isn't prime.

(2^33-1)(2^33+1) = 2^66 -1 implies 2^66 -1 isn't prime

Reply 12

andrewk

OP

generalebriety

I think you mean you're meant to prove that

2^{66} - 1

isn't prime?

Let x = 2^33. Show that your number has at least one factor which isn't 1 or 2^66 - 1 itself, and you've shown it's not prime.

Thanks ye it was supposed to be

2^{66}-1

ok so i change x to

2^{33}

and type it into my calculator and it gives me the answer

7.378697629*10^{19}

so how do i use this to prove it isn't a prime number?

Also as pointed out the original number is even so how would this work for an odd number? e.g.

2^{67}

Stupidity alert. Do not read further.

2^{66} - 1 = (2^{33} + 1) (2^{33} - 1)

by the difference of 2 squares.

2^{33}

is even as it is a multiple of 2.

so

2^{33} + 1

is odd as is

2^{33} - 1

.

Two odd numbers multiplied together produce an odd number.

Hence

2^{66} - 1

must be odd.

Which tells you absolutely nothing about anything cos we can see that from the question.

Reply 14

sonofdot

8

Mr M

I suspect the OP still doesn't understand!

Here's an accessible argument.

2^{66} - 1 = (2^{33} + 1) (2^{33} - 1)

by the difference of 2 squares.

2^{33}

is even as it is a multiple of 2.

so

2^{33} + 1

is odd as is

2^{33} - 1

.

Two odd numbers multiplied together produce an even number.

Hence

2^{66} - 1

must be even.

As it even (and not two!) it is not prime.

Bet he gets it now!

someone's not awake today... :p:

Reply 15

alexmahone

Mr M

I suspect the OP still doesn't understand!

Here's an accessible argument.

2^{66} - 1 = (2^{33} + 1) (2^{33} - 1)

by the difference of 2 squares.

2^{33}

is even as it is a multiple of 2.

so

2^{33} + 1

is odd as is

2^{33} - 1

.

Two odd numbers multiplied together produce an even number.
Hence

2^{66} - 1

must be even.

As it even (and not two!) it is not prime.

Bet he gets it now!

Mind giving an example? :biggrin:

Reply 16

Zhen Lin

12

... no, the product of two odd numbers is another odd number.

The point of being able to do a difference of two squares factorisation is being able to find non-trivial factors of

2^{66} - 1

.

2^{33} + 1 > 2^{33} - 1 > 1

, hence, we have found the required non-trivial factors of

2^{66} - 1

, therefore it is not prime.

Oh I get it!

Duh.

Just factorising it is enough!

Bet the OP STILL doesn't understand though if he was trying to type numbers into his calc.

Reply 18

Sallena

the reason your calculator wont help is because you wont be able to see if numbers that large are integers or not.
you have found that the number can be factorised into (2^33+1)(2^33-1). So all you need to know now is if those two factors are integers. If they are, 2^66-1 cant be a prime as it is divisible by more than 2 numbers (the others being 1 and the number itsself). 2^33 is an integer and adding/subtraction 1 doesnt change this.

Reply 19

andrewk

OP

Mr M

Oh I get it!

Duh.

Just factorising it is enough!

Bet the OP STILL doesn't understand though if he was trying to type numbers into his calc.

Ye im still a little confused but i think im getting there (slowly) basically factorisng it proves it is an even number which obviously can't be a prime number?

So what happens if the number is odd?

Prime numbers

Related discussions

Latest

Trending

Trending

Articles for you