corollary of Kummer’s theorem

As shown in Kummer’s theorem, the power of a prime numberMathworldPlanetmath p dividing (nm),nm, was the total number of carries when adding m and n-m in base p. We’ll give a recurrence relationMathworldPlanetmath for the carry indicator.

Given integers nm0 and a prime number p, let ni,mi,ri be the i-th digit of n,m, and r:=n-m, respectively.

Define c-1=0, and

ci={1if mi+rip,0otherwise

for each i0 up to the number of digits of n.

For each i0 we have

Starting with the i-th digit of n, we multiply with increasing powers of p to get


The last sum in the above equation leaves only the values for indices i and d, and we get

npi=mpi+rpi+ci-1 (1)

for all i0.

Title corollary of Kummer’s theorem
Canonical name CorollaryOfKummersTheorem
Date of creation 2013-03-22 13:23:07
Last modified on 2013-03-22 13:23:07
Owner Thomas Heye (1234)
Last modified by Thomas Heye (1234)
Numerical id 7
Author Thomas Heye (1234)
Entry type Corollary
Classification msc 11A63