1. ## 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......

2. ## Re: Determining primality

Originally Posted by jamix
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...

3. ## Re: Determining primality

Originally Posted by ILikeSerena
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.

4. ## Re: Determining primality

Oops. I made a calculation mistake myself.
I'll have to think about it some more.

5. ## 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.

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.

6. ## 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.

7. ## Re: Determining primality

Originally Posted by Mouhaha
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?

Originally Posted by Mouhaha
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.