Prime or composite?

Dec 2009
411
131
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 ;)
 
Dec 2009
411
131
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).
 
  • Like
Reactions: TheCoffeeMachine
Nov 2009
927
260
Wellington
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 \(\displaystyle 2438100000001 = x^5 + x^4 + 1\) ? xD
 
Oct 2007
722
168
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 \(\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\)
 
  • Like
Reactions: Dinkydoe
Dec 2009
411
131
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

\(\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?
 
Nov 2009
485
184
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\).
 
  • Like
Reactions: Dinkydoe
Nov 2009
927
260
Wellington
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 (Giggle)

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.
 
  • Like
Reactions: Dinkydoe
Nov 2009
485
184
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 (Giggle)
I thought that pencil and paper was okay.