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
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 , with , as a first observation. However, normal people don't just 'notice' this.
There's however much simpler arguments. (Hopefully also even harder arguments).
May I use the computer to reply ?Is the number 2438100000001 prime or composite? No calculators or computers allowed!
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 ? xD
Haha, exactly my point ;phow the hell are we supposed to somehow notice that 2438100000001 = x^5 + x^4 + 1 ? xD
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
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 with .
I don't fully understand the proof, but the simpel observation that seems to me enough.
then , and are both factors, so the number is not prime.
Can you guys prove that 139801079 is composite without using the help of a computer?
I didn't know you could compute a GCD of magnitude mentally. You'll have to tell me how to do it
This is the steps I follow when attempting to determine the factors of a number :Can you guys prove that 139801079 is composite without using the help of a computer?
- 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.
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 . Therefore the number is divisable by 11. XD
A proof of this little trick:
we can write
Therefore if this sum is divisable by 11 so was the original number
You can find some exposition on the rho method on Wikipedia: Pollard's rho algorithm - Wikipedia, the free encyclopedia
Quite a handy little algorithm.