1. ## Prime or composite?

Hee, I saw this cute puzzle somewhere:

Is the number 2438100000001 prime or composite? No calculators or computers allowed!

It's not a very hard puzzle, but still I'm curious what creative ways you guys will find to come to your answers.

I found a much simpler argument then the original answer provided, but it's ofcourse much more fun to do this with some funky math

2. Yeah wilmer, finding the original answer on internet isn't that hard. Can you come up with any other way to prove this yourself?

I found the answer provided very original, but I had some objections to this:
It's used that $\displaystyle 2438100000001 = x^5 + x^4 + 1$, with $\displaystyle x = 300$, as a first observation. However, normal people don't just 'notice' this.

There's however much simpler arguments. (Hopefully also even harder arguments).

3. Is the number 2438100000001 prime or composite? No calculators or computers allowed!
May I use the computer to reply ?

I have a marvellous proof for this problem which this textbox is too narrow to contain.

Honestly, I don't know, there might be some mathematical trick that can be used here mentally, but I don't see how to do it without at least performing some operations of the same order of magnitude as the number. And the solution given in Wilmer's link is fallacious : how the hell are we supposed to somehow notice that $\displaystyle 2438100000001 = x^5 + x^4 + 1$ ? xD

4. Originally Posted by Bacterius
May I use the computer to reply ?

I have a marvellous proof for this problem which this textbox is too narrow to contain.

Honestly, I don't know, there might be some mathematical trick that can be used here mentally, but I don't see how to do it without at least performing some operations of the same order of magnitude as the number. And the solution given in Wilmer's link is fallacious : how the hell are we supposed to somehow notice that $\displaystyle 2438100000001 = x^5 + x^4 + 1$ ? xD
I though the same but actually...

$\displaystyle 243 = 3^5$

$\displaystyle 81 = 3^4$

but we actually have 243 with 10 zeros after it (ignoring the one) which we can think of as $\displaystyle 100^5$

Same with the 81. There's 8 zeros after that which is $\displaystyle 100^4$

So we get $\displaystyle 3^5 100^5 + 3^4 100^4 + 1 = 2438100000001$

=> $\displaystyle 300^5 + 300^4 + 1 = 2438100000001$

5. how the hell are we supposed to somehow notice that 2438100000001 = x^5 + x^4 + 1 ? xD
Haha, exactly my point ;p

Actually I'm somewhat embarassed to say this. But I noticed I made an error in my argument so I'll be breaking my head over this one too. However my argument works for other large numbers. So I'll make a number myself, and change the puzzle ;p

Wolframalpha gives the prime-factorisation

$\displaystyle 73\times829\times1237\times32569$

I find it somewhat an odd puzzle, cause I don't think any normal human being is going to prove that the number is composite without knowing any of the prime-factors beforehand.

The answer however provided in Wilmer's link is not fallacious. I found it somewhat a clever trick. But with a inhuman observation that the number can be written as $\displaystyle f(x)=x^5+x^4+1$ with $\displaystyle x=300$.

I don't fully understand the proof, but the simpel observation that $\displaystyle f(x)=(x^2+x+1)(x^3-x+1)$ seems to me enough.

then $\displaystyle 300^2+300+1 = 90301$, and $\displaystyle 300^3-300+1= 26999701$ are both factors, so the number is not prime.

Can you guys prove that 139801079 is composite without using the help of a computer?

6. I would probably just do something like Pollard's rho method to get a factor, since the number doesn't look too bad.

Set $\displaystyle f(x)=x^2+1$ and $\displaystyle n=139801079$. Pick some starting values $\displaystyle x=2, y=2$. Then,

$\displaystyle x_1=f(x)=5$
$\displaystyle y_1=f(f(y))=26$
$\displaystyle \gcd(26-5,139801079)=1$

$\displaystyle x_2=f(x_2)=26$
$\displaystyle y_2=f(f(y_1))=458304$
$\displaystyle \gcd(458304,139801079)=11$

Therefore, $\displaystyle 139801079$ is not prime and has a factor of $\displaystyle 11$.

7. Hi Roninpro,
I didn't know you could compute a GCD of magnitude $\displaystyle 10^6$ mentally. You'll have to tell me how to do it

Can you guys prove that 139801079 is composite without using the help of a computer?
This is the steps I follow when attempting to determine the factors of a number :

- Trial on the first 30 primes (256 if computer)
- Fermat's method
- Trial square congruence
- Pollard's rho
- Pollard's p-1 (if computer)
- William's p+1 (if computer)
- ECM (if computer)
- dammit this is a hard one, GNFS (if computer)
- return failure

Unfortunately, the second number you submitted failed to pass the first stage. 11 is indeed a factor of 139801079.

Although after having factorized it completely, I see that let alone the 11, the two remaining factors are really close to each other, which would have made Fermat's method successful after having removed the 11.

8. Originally Posted by Bacterius
Hi Roninpro,
I didn't know you could compute a GCD of magnitude $\displaystyle 10^6$ mentally. You'll have to tell me how to do it
I thought that pencil and paper was okay.

9. Originally Posted by roninpro
I thought that pencil and paper was okay.
It still is quite time consuming isn't it ?

I could do a paper and pencil Miller Rabin if time isn't relevant

Roninpro, I don't quite understand the method you're using but it looks
like some long-division algorithm. I'll be interested in how it works.

I had another cute little method to show that 139801079 is divisable by 11.
A little test you can allways try:

we can sum the digits like $\displaystyle 9-7+0-1+0-8+9-3+1= 0$. Therefore the number is divisable by 11. XD

A proof of this little trick:

we can write $\displaystyle n= a_n10^n+a_{n-1}10^{n-1}+\cdots 10a_1+a_0\equiv \sum_n (-1)^na_n (\text{mod}) 11$

Therefore if this sum is divisable by 11 so was the original number

11. You can find some exposition on the rho method on Wikipedia: Pollard's rho algorithm - Wikipedia, the free encyclopedia

Quite a handy little algorithm.