# Prime or composite?

• May 12th 2010, 01:13 PM
Dinkydoe
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 ;)
• May 12th 2010, 08:26 PM
Wilmer
• May 13th 2010, 03:27 AM
Dinkydoe
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 $2438100000001 = x^5 + x^4 + 1$, with $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).
• May 15th 2010, 07:07 AM
Bacterius
Quote:

Is the number 2438100000001 prime or composite? No calculators or computers allowed!
May I use the computer to reply ? (Giggle)

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 $2438100000001 = x^5 + x^4 + 1$ ? xD
• May 15th 2010, 07:52 AM
Quote:

Originally Posted by Bacterius
May I use the computer to reply ? (Giggle)

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 $2438100000001 = x^5 + x^4 + 1$ ? xD

I though the same but actually...

$243 = 3^5$

$81 = 3^4$

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

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

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

=> $300^5 + 300^4 + 1 = 2438100000001$
• May 15th 2010, 12:09 PM
Dinkydoe
Quote:

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

$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 $f(x)=x^5+x^4+1$ with $x=300$.

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

then $300^2+300+1 = 90301$, and $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?
• May 16th 2010, 05:06 PM
roninpro
I would probably just do something like Pollard's rho method to get a factor, since the number doesn't look too bad.

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

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

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

Therefore, $139801079$ is not prime and has a factor of $11$.
• May 16th 2010, 08:00 PM
Bacterius
Hi Roninpro,
I didn't know you could compute a GCD of magnitude $10^6$ mentally. You'll have to tell me how to do it (Giggle)

Quote:

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.
• May 17th 2010, 07:00 AM
roninpro
Quote:

Originally Posted by Bacterius
Hi Roninpro,
I didn't know you could compute a GCD of magnitude $10^6$ mentally. You'll have to tell me how to do it (Giggle)

I thought that pencil and paper was okay.
• May 17th 2010, 12:18 PM
Bacterius
Quote:

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 :D
• May 24th 2010, 11:45 AM
Dinkydoe

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 $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 $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
• May 24th 2010, 12:24 PM
roninpro
You can find some exposition on the rho method on Wikipedia: Pollard's rho algorithm - Wikipedia, the free encyclopedia

Quite a handy little algorithm.