# Prime or composite?

#### Dinkydoe

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

#### 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 $$\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).

TheCoffeeMachine

#### Bacterius

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

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

Dinkydoe

#### Dinkydoe

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?

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

Dinkydoe

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

Dinkydoe

#### roninpro

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.

#### Bacterius

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