0

I have a question about the following method...

Q) Show that the number $2^{64} -1$ is not a prime.

Working:

If $2^{64} -1$ is a prime then it's only factors are 1 and itself $2^{64} -1 =(2^{32})^2 -1^2$ , using DOTS=$(2^{32}+1)(s^{32}-1)$ So $(2^{32}+1)$ and $(s^{32}-1)$ are factors of $2^{64} -1$.

I understand up to here, but not the following:

So if $(2^{32}+1)$ and $(s^{32}-1)$ are factors then why isn't it a prime as it is being techincally being divided by itself? If someone could show how to prove why this is not a prime that would be much appreciated.

Siong Thye Goh
  • 149,520
  • 20
  • 88
  • 149
Fred
  • 133
  • A prime number has a few definitions, but either as a consequence of the definition or as the definition itself we have that a prime integer is one whose only positive factors are $1$ and itself. That is to say, the only way you can multiply two positive integers and get a prime number, one of those things must be $1$ and the other the number itself. A number which is not prime is composite, and composite numbers can always be written as the product of two smaller numbers, neither of which are equal to $1$. You say that $2^{64}-1=(2^{32}+1)(2^{32}-1)$ which is correct. So... – JMoravitz Sep 15 '17 at 19:25
  • 1
    Using a smaller example, $2^4-1=15=(2^2+1)(2^2-1)=5\cdot 3$. Neither of $5$ nor $3$ are equal to $1$ or $15$. – JMoravitz Sep 15 '17 at 19:28

1 Answers1

0

$(2^{32}\pm1)$ is a integer and it divides $ 2^{64}-1$$$$$ For eg,$$$$ $$\frac{2^{64}-1}{2^{32}-1}=\frac{(2^{32}+1)(2^{32}+1)}{2^{32}-1}=2^{32}+1$$ Hence divisible by $(2^{32}-1)$$$$$ We can give similar proof for $(2^{32}+1)$$$$$ And prime no. is defined as no. which is only divisible by 1 and itself

neonpokharkar
  • 1,834