Just Johan |
05-12-2002 20:29 |
Ja, moet je de tafel van 8 eens bekijken in het 9-talligstelsel:
8, 17, 26, 35, 44, 53, 62, 71, 80 :p
We kunnen ook wel even bewijzen dat je in het algemeen kunt stellen dat de som van een veelvoud van (g-1) in het g-tallig stelsel een veelvoud van (g-1) is, nu ik toch nog maar twee strikte deadlines heb voor morgenochtend ;)
A) We beginnen met een triviaal geval; 1*(g-1) heeft duidelijk een som van digits gelijk aan (g-1).
B) Stel het geldt voor n*(g-1), klopt het dan automatisch voor (n+1)*(g-1)? (als dat zo is dan klopt het dus voor iedere n, want omdat het voor n=1 geldt, geldt het ook voor n=2; en omdat het voor n=3 geldt, geldt het automatisch ook voor n=4 en zo oneindig lang door)
We onderscheiden 2 gevallen:
B.1) De laatse digit is 0; er komt (g-1) voor in de plaats en de totale som blijft dus een veelvoud van (g-1)
B.2) De laatste digit is ongelijk 0; noem die d1; deze is dus ook d1 modulo g; als we daar (g-1) bij optellen krijgen we:
d1-1+g modulo g = d1-1 modulo g; we verliezen hier dus eigenlijk 1, maar er is ook een carry van 1. We onderscheiden opnieuw twee gevallen:
B.2.1) De digit ervoor is ongelijk (g-1); we tellen de carry van 1 erbij op en de som van de digits is een veelvoud van (g-1) plus 1 min 1; ofwel een veelvoud van (g-1) en het klopt alsnog.
B.2.2) De digit ervoor is gelijk aan (g-1); deze digit wordt 0; wat een verlies van (g-1) betekent (wat geen verschil maakt in het al of niet zijn van een veelvoud van (g-1) voor het hele getal) en er is opnieuw een carry van 1 waarvoor we opnieuw bekijken of B.2.1 of B.2.2 van toepassing is. Dit proces is eindig want de lengte van het getal is eindig :)
|