| brain activity log
02.01.2007 - Tuesday - 02:55 - Primality Tests
Happy New Year to everyone :)
At a certain point, in the middle of the New Year party we ended up
talking about prime numbers. The simple question was if 2007 was prime or not.
A guy immediately comed out with the answer: no, it's divisible by 3.
He used a simple "rule of thumb": if the digits of a number sum up
to something that is divisible by 3 then the original number is also divisible by 3.
And in fact 2+0+0+7 yelds 9 that is obviously 3*3.
So 2007 is not a prime year. But how is it that the rule of thumb works ?
We were quite convinced that the rule is correct by carrying out
a ton of working examples but (probably because of alcohol :D) were unable
to prove it.
In fact a pedantic proof is not as trivial as one might expect for such a simple rule.
Anyway, a bit of thinking (with a sane mind) pulled it out. Here it is.
Theorem
Given an integer x let y be the sum of its decimal digits. If y is divisible
by 3 then x is also divisible by 3 and vice-versa.
Since for x=0 the theorem is trivially true, let x be a non-zero integer and consider
it's positional rappresentation:
The digits di in the sum are obviously the positional digits of x
ordered by magnitude (power of ten). Let y be the sum of the digits of x.
Asserting that "if y is divisible by 3 then x is also divisible by 3 and vice-versa"
is equivalent to asserting that "if there exists an integer w that yelds x=3w then
there must exist an integer v that yelds y=3v and vice-versa".
A yet more convenient way to formally state the theorem thesis is: given
prove that "if w lies in Z then also v lies in Z and vice-versa".
To prove this let's concentrate on the positional rappresentation of our number.
We can trivially rewrite it as
which can be decomposed in
which clearly shows that the second component is the sum of the digits defined above
and allows us to write
and then rewrite it further as
Now if we assume that w is an integer then v is an integer (lies in Z)
if and only if
The same condition remains if we first assume v to be an integer
and ask for w being an integer: it still
leads us to prove that
Now if you're cool, you should have already be "seeing" the end of this
proof since the formula above can be "trusted" to be true if you realize
that 10^i - 1 leads always to a number with digits formed by a sequence
of all 9.... but let's be pedantic and prove this formally.
To do this we need to take a quick look at a nice property of the foolowing
geometric serie:
We can multiply both sides by (a-1) to obtain
Expliciting the multiplication
and removing the cancelling terms we get
which is quite interesting since by plugging in a=10 it allows us to write that
and for i=k+1 -> k=i-1 it allows to rewrite our clue formula as
and then by trivial algebric manipulation
Remember that in the formulas above we have assumed x != 0 (since, as stated at the beginning,
for x=0 the theorem is trivially true). This in turn requires i > 0 and
thus i-1 is at least 0.
Finally since  , since 10^j is
an integer and a sum of integers is still an integer it's obvious that
which proves our theorem.
Cool eh? What a strange world... :)
It is interesting to state that this thingie can be applied recursively.
If y is too big to be trivially known to be divisible by 3 then
the sum of its digits can be taken and the theorem can be applied again.
Another note is that the theorem will work for bases B that can be written
in the form B=3N+1 where N is an integer. It will work for base 4, 7, 10,
13, 16... but not for base 2 (for example). This can be proven by substituting
(3N+1) in the whole theorem in place of 10 and noticing that it will lead
us to prove that
The geometric serie property is still valid and yelds
which is rewritten as
This allows us to rewrite our question as
which, since di and N are integers, yelds the obvious conclusion that
Marvellous...
One can push this thingie even further and assert that to verify
the divisibility by a number D one has to write the number x in a base B
that can be written as B=(DN+1), where N is an integer greater than zero,
sum up the digits of B and verify if the obtained number is divisible by D.
This can be proven by reusing the
last version of the theorem and plugging D instead of 3. The question
will now be
And it will lead us to state that
Which is indeed true since D, N and di are integers.
Interesting. So if you want to know if 3147975 is divisible
by 255 all you could write 3147975 in a base of the form 255N+1,
for example 256 (huh.. we're talking of BYTES!), sum up the digits
and check if it's divisible by 255, recursively.
3147975 is (48)(8)(199) in base 256 which magically sums up to 255.... doh!
I could have written this thingie in base 255*2+1=511, which would yeld
a rappresentation of (12)(28)(215) which again sums up to 255.
Unbelieveable...
The bad news, eventually, is that this theorem can't be easily used
as a general primality test since it involves base changes. A generic change
from base A to base B requires consecutive divisions of the original
number... so one can actually directly divide the number by the divisor
and check if there is a remainder...
This can be used as primality test for some divisors,
in particular the ones that lead to the bases B to which switching
is easy. Switching from base 10 to base 100 is straightfoward and
does not require any division to be performed. Same goes for base 2 and base 16,
for example.
Now I have to work. Further investigations later.
Have a nice day!
want more ?
... really ? :D
Browse around then.
You're viewing one post per page: you can view more, if you want.
The entries marked in red are the ones you're viewing now.
| 
