Thread: Proving a Pseudoprime?

How can I prove that the number 1729 is a pseudoprime ? I know that a pseudoprime is a composite n where n|((2^n)-2).

Originally Posted by 1337h4x

How can I prove that the number 1729 is a pseudoprime ? I know that a pseudoprime is a composite n where n|((2^n)-2).

Just take modulo .

Originally Posted by chiph588@

Just take [tex] 2^{1729}-2 [tex] modulo .

Could you please recheck your formatting because I'm having trouble distinguishing what this means.

Also, If you're saying just do the operation, that really doesn't qualify as a proof, isn't that just an evaluation? How would I prove it?

Originally Posted by 1337h4x

Could you please recheck your formatting because I'm having trouble distinguishing what this means.

Also, If you're saying just do the operation, that really doesn't qualify as a proof, isn't that just an evaluation? How would I prove it?

You want to show that .

Originally Posted by chiph588@

You want to show that .

How do I show that?

Isn't that ?

Originally Posted by 1337h4x

How can I prove that the number 1729 is a pseudoprime ? I know that a pseudoprime is a composite n where n|((2^n)-2).

As you already wrote, you only need to evaluate (basically, verify that 1729 fulfills the definition).
You should be familiar with [ur=http://en.wikipedia.org/wiki/Modular_arithmetic]modular arithmetics[/url] and congruences to do this.

Whether you want to this by hand or by computer, an effective way is to compute powers for the exponents:
1729 -> 864 -> 432 -> 216 -> 108 -> 54 -> 27 -> 13 -> 6 -> 3 -> 1
(If you already know n-th power, then you can easily compute (2n)-th power, and by multiplying by 2, you get the (2n+1)-st power.)
This method is described in this wikipedia article.

For instance, you can start as




etc.