0

Can Someone please help me prove that the number 1729 is a Pseudoprime?

So a pseudoprime is a composite $n$ such that $n |(2^n − 2)$. And every prime number also has this property.

Ryan Sole
  • 1

2 Answers2

1

$2^{1729}-2=2(2^{1728}-1).$ And $1729=7\cdot 13 \cdot 19.$ Check that each of $6,12,18$ (each one less than the primes $7,13,19$) divide the exponent $1728.$ So (using Fermat's "Little Theorem" here) $2^{1728}-1$ is divisible by the product $7 \cdot 13 \cdot 19 = 1729.$ Hence if we double this we get $1729$ being a divisor of $2^{1729}-2.$

coffeemath
  • 29,884
  • 2
  • 31
  • 52
  • So since 6 divides 1728, 12 divides 1728 and 18 divides 1728, it works. So we are done, right? – Ryan Sole Feb 07 '15 at 17:51
  • Yes, but bring out the connection with Fermat Theorem, that $a^{p-1}=1$ mod $p$ (provided $\gcd(a,p)=1$ which holds here since $a=2$ and each prime $7,13,19$ is odd.) Since for example $1728=6 \cdot 288$ we can say mod 7 that $2^{1728}=(2^6)^{288}=1^{288}=1$ in mod $7$ so finally get $2^{1728}-1$ divisible by $7$. [I'm just saying some care needed in write-up.] Also used that if each of $7,13,19$ divides something so does their product. – coffeemath Feb 07 '15 at 18:21
1

While coffeemath's proof is pretty much correct, I thought it might be more useful to expand on the mechanics of what he's doing.

Because $n|2^n-2$, we know that $2^n\equiv2 \pmod{n}$. This can be restated as $2^{n-1} \equiv 1 \pmod{n}$ (here $gcd(2,n)=1$)

So we want to show that $2^{1728}\equiv1\pmod{1729}$

Let's leave that there. Now, we can see that $1729=7*13*19$, so any number divisible by all three of those numbers, which are all relatively prime, is also divisible by $1729$.

Now the Chinese remainder theorem tells us that there exists $x$ such that $$x\equiv1\pmod{7}$$ $$x\equiv1\pmod{13}$$ $$x\equiv1\pmod{19}$$ and that $x$ is a solution$\pmod{1729}$. Now, this is where Fermat's Little Theorem comes into play. We know from Fermat's LT that: $$2^6\equiv1\pmod{7}$$ $$2^{12}\equiv1\pmod{13}$$ $$2^{18}\equiv1\pmod{19}$$ Ok, so what? well observe that $6*288=12*144=18*96=1728$. Now using the fact that if $a\equiv b\pmod{n}$, then $a^k\equiv b^k\pmod{n}$, we can see that:

$$2^{6*288}\equiv1^{288}\pmod{7}$$ $$2^{12*144}\equiv1^{144}\pmod{13}$$ $$2^{18*96}\equiv1^{96}\pmod{19}$$

So $2^{1728}\equiv1\pmod{7,13, 19}$. Thus, $x=2^{1728}$ is a solution to the system from the CRT. So $2^{1728}\equiv1\pmod{1729}$

bumblyboi
  • 95
  • 4