Results 1 to 12 of 12

Math Help - Prime or composite?

  1. #1
    Senior Member Dinkydoe's Avatar
    Joined
    Dec 2009
    Posts
    411

    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
    Follow Math Help Forum on Facebook and Google+

  2. #2
    MHF Contributor
    Joined
    Dec 2007
    From
    Ottawa, Canada
    Posts
    3,106
    Thanks
    68
    Follow Math Help Forum on Facebook and Google+

  3. #3
    Senior Member Dinkydoe's Avatar
    Joined
    Dec 2009
    Posts
    411
    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).
    Follow Math Help Forum on Facebook and Google+

  4. #4
    Super Member Bacterius's Avatar
    Joined
    Nov 2009
    From
    Wellington
    Posts
    927
    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
    Follow Math Help Forum on Facebook and Google+

  5. #5
    Super Member Deadstar's Avatar
    Joined
    Oct 2007
    Posts
    722
    Quote Originally Posted by Bacterius View Post
    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
    Follow Math Help Forum on Facebook and Google+

  6. #6
    Senior Member Dinkydoe's Avatar
    Joined
    Dec 2009
    Posts
    411
    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?
    Follow Math Help Forum on Facebook and Google+

  7. #7
    Senior Member roninpro's Avatar
    Joined
    Nov 2009
    Posts
    485
    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.
    Follow Math Help Forum on Facebook and Google+

  8. #8
    Super Member Bacterius's Avatar
    Joined
    Nov 2009
    From
    Wellington
    Posts
    927
    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.
    Follow Math Help Forum on Facebook and Google+

  9. #9
    Senior Member roninpro's Avatar
    Joined
    Nov 2009
    Posts
    485
    Quote Originally Posted by Bacterius View Post
    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.
    Follow Math Help Forum on Facebook and Google+

  10. #10
    Super Member Bacterius's Avatar
    Joined
    Nov 2009
    From
    Wellington
    Posts
    927
    Quote Originally Posted by roninpro View Post
    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
    Follow Math Help Forum on Facebook and Google+

  11. #11
    Senior Member Dinkydoe's Avatar
    Joined
    Dec 2009
    Posts
    411
    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
    Follow Math Help Forum on Facebook and Google+

  12. #12
    Senior Member roninpro's Avatar
    Joined
    Nov 2009
    Posts
    485
    You can find some exposition on the rho method on Wikipedia: Pollard's rho algorithm - Wikipedia, the free encyclopedia

    Quite a handy little algorithm.
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. Replies: 1
    Last Post: October 22nd 2011, 12:37 PM
  2. Replies: 1
    Last Post: June 19th 2011, 12:56 PM
  3. Prove composite number has a prime divisor
    Posted in the Number Theory Forum
    Replies: 3
    Last Post: January 25th 2011, 04:44 PM
  4. Replies: 7
    Last Post: January 6th 2011, 07:23 PM
  5. prime or composite
    Posted in the Algebra Forum
    Replies: 7
    Last Post: October 23rd 2008, 09:17 AM

Search Tags


/mathhelpforum @mathhelpforum