Results 1 to 7 of 7

Math Help - Determining primality

  1. #1
    Member
    Joined
    Jun 2008
    Posts
    148

    Determining primality

    Consider summing the digits of the number 141. We have 1 + 4 + 1 = 6. You might remember the rule that if the "sum of the digits" of some integer N is divisible by 3, then the original integer is also divisible by 3 (in the case 141 = 47 x 3).......

    Now instead of determining divisibility by 3, consider the problem of determining the primality of the "sum of the digits" of some integer N that is written in base B.

    In particular, consider base B = 7. Under this base, the integer 7 will be represented as 10. The sum of its digits will be 1 + 0 = 1.

    .................................................. ....................................

    Prove that if an integer N is prime and is written in base 7, then the sum of its digits is always prime (excluding the example 7 above). If it is not true, find a counter-example......
    Follow Math Help Forum on Facebook and Google+

  2. #2
    Super Member ILikeSerena's Avatar
    Joined
    Dec 2011
    Posts
    733
    Thanks
    121

    Re: Determining primality

    Quote Originally Posted by jamix View Post
    Consider summing the digits of the number 141. We have 1 + 4 + 1 = 6. You might remember the rule that if the "sum of the digits" of some integer N is divisible by 3, then the original integer is also divisible by 3 (in the case 141 = 47 x 3).......

    Now instead of determining divisibility by 3, consider the problem of determining the primality of the "sum of the digits" of some integer N that is written in base B.

    In particular, consider base B = 7. Under this base, the integer 7 will be represented as 10. The sum of its digits will be 1 + 0 = 1.

    .................................................. ....................................

    Prove that if an integer N is prime and is written in base 7, then the sum of its digits is always prime (excluding the example 7 above). If it is not true, find a counter-example......
    Hi jamix!

    Have you tried to find a counter example?
    Suppose you list all primes up to say 40.
    Do they all fit the pattern?

    Btw, it's not easy to construct primes, so any algorithm that says so is suspect...
    Follow Math Help Forum on Facebook and Google+

  3. #3
    Member
    Joined
    Jun 2008
    Posts
    148

    Re: Determining primality

    Quote Originally Posted by ILikeSerena View Post
    Hi jamix!

    Have you tried to find a counter example?
    Suppose you list all primes up to say 40.
    Do they all fit the pattern?

    Btw, it's not easy to construct primes, so any algorithm that says so is suspect...
    The primes up to 101 written in base 7 are as follows;

    2
    3
    5
    10
    14
    16
    23
    25
    32
    41
    43
    52
    56
    61
    65
    104
    113
    115
    124
    131
    133
    142
    146
    155
    166
    203

    If you add the digits in each of these integers, you get a prime number!

    I suspect there is a counter example higher up, but I haven't been able to download a program like PARI or something else that will let me test millions of numbers very quickly. Keep in mind that this algorithm can only construct smaller prime integers from bigger ones.
    Follow Math Help Forum on Facebook and Google+

  4. #4
    Super Member ILikeSerena's Avatar
    Joined
    Dec 2011
    Posts
    733
    Thanks
    121

    Re: Determining primality

    Oops. I made a calculation mistake myself.
    I'll have to think about it some more.
    Follow Math Help Forum on Facebook and Google+

  5. #5
    Junior Member
    Joined
    Dec 2012
    From
    Canada Ontario
    Posts
    43

    Re: Determining primality

    It is true even for some composite numbers

    2875 (base 10)=11245(base 7)

    The sum of digits is 13 which is prime but 2875 is NOT prime.

    So it is not helpful.
    It is like saying that if n>2 is prime then n is ALWAYS odd.

    Nothing new HERE. The prime number need some very deep tool to reveal its secrets.
    Last edited by Mouhaha; March 2nd 2013 at 11:09 AM.
    Follow Math Help Forum on Facebook and Google+

  6. #6
    Junior Member
    Joined
    Dec 2012
    From
    Canada Ontario
    Posts
    43

    Re: Determining primality

    Counterexample :

    99991 is prime base 10

    99991=564343(base7)

    The sum of 564363 is = 5+6+4+3+4+3= 25 which is not prime

    I think that there are an infinite number of counterexamples.
    Follow Math Help Forum on Facebook and Google+

  7. #7
    Member
    Joined
    Jun 2008
    Posts
    148

    Re: Determining primality

    Quote Originally Posted by Mouhaha View Post
    Counterexample :

    99991 is prime base 10

    99991=564343(base7)

    The sum of 564363 is = 5+6+4+3+4+3= 25 which is not prime

    I think that there are an infinite number of counterexamples.
    Thanks Mouhaha, that number is huge! Was 99991 the smallest one?


    Quote Originally Posted by Mouhaha View Post
    It is true even for some composite numbers

    2875 (base 10)=11245(base 7)

    The sum of digits is 13 which is prime but 2875 is NOT prime.

    So it is not helpful.
    It is like saying that if n>2 is prime then n is ALWAYS odd.

    Nothing new HERE. The prime number need some very deep tool to reveal its secrets.
    Not even the Fermat test is perfect and deterministic primality tests are time consuming. A more important question is what PERCENTAGE of composite integers fail this test?
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. Primality Criteria for F_n(2336)
    Posted in the Number Theory Forum
    Replies: 0
    Last Post: March 21st 2012, 07:36 AM
  2. The fastest way to test primality ?
    Posted in the Number Theory Forum
    Replies: 4
    Last Post: December 9th 2011, 09:00 AM
  3. Wilson's Primality Test ... what ?
    Posted in the Math Forum
    Replies: 3
    Last Post: June 9th 2010, 06:44 AM
  4. [HELP]Relative Primality in the Following Algorithm
    Posted in the Number Theory Forum
    Replies: 0
    Last Post: October 28th 2008, 06:37 AM
  5. primality testing - ugh - HELP
    Posted in the Advanced Algebra Forum
    Replies: 1
    Last Post: September 16th 2007, 08:26 PM

Search Tags


/mathhelpforum @mathhelpforum