Prime or composite?

**Dinkydoe** · May 12th 2010, 01:13 PM

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

**Wilmer** · May 12th 2010, 08:26 PM

2438100000001 - Google Search=

**Dinkydoe** · May 13th 2010, 03:27 AM

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).

**Bacterius** · May 15th 2010, 07:07 AM

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

**Deadstar** · May 15th 2010, 07:52 AM

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 $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$

**Dinkydoe** · May 15th 2010, 12:09 PM

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

About the original puzzle:

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?

**roninpro** · May 16th 2010, 05:06 PM

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$ .

**Bacterius** · May 16th 2010, 08:00 PM

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

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)
- Quadratic sieve (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.

**roninpro** · May 17th 2010, 07:00 AM

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

I thought that pencil and paper was okay.

**Bacterius** · May 17th 2010, 12:18 PM

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

**Dinkydoe** · May 24th 2010, 11:45 AM

Thank you all for your comments,

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

**roninpro** · May 24th 2010, 12:24 PM

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

Quite a handy little algorithm.

Thread: Prime or composite?

LinkBack

Thread Tools

Display

Prime or composite?

Similar Math Help Forum Discussions

Using the fact that a pair of numbers is relatively prime to prove that one is prime

Prove that if n>=2 and not prime, then n has a prime divisor p<=(sq.root)n

Prove composite number has a prime divisor

[SOLVED] Universal and existential statements for prime and composite numbers(proof)

prime or composite

Search Tags