Bewijzen

Antwoorden bij de opgaven

1. `a^2 - 1 = (a - 1)(a + 1)`
2. `a - 1` is de voorganger van `a` en `a + 1` de opvolger. Omdat `a` oneven is, zijn die getallen even.
3. Van twee opeenvolgende even getallen is altijd één beide deelbaar door 4.
4. Omdat zowel `a - 1` als `a + 1` even getallen zijn en één van beide een viervoud is, kun je hun product delen door `4 * 2 = 8`.
Beide zijden delen door `1 - x` mag niet omdat je dan door 0 deelt, immers `x = 1` was je uitgangspunt!
Er zijn vier mogelijkheden:
- `n` en `m` zijn beide even, dan is `n*m` deelbaar door `2*2` en dus even;
- `n` is even een `m` niet, dan is `n * m` deelbaar door 2 en dus even;
- `n` is oneven en `m` is even, dan is `n * m` deelbaar door 2 en dus even;
- `n` en `m` zijn beide oneven, dan is `n * m` niet deelbaar door 2.
Dus de enige mogelijkheid voor `n * m` om oneven te zijn is als zowel `n` als `m` oneven is. Hier kun je ook heel goed een indirect bewijs gebruiken...
1. Zie Voorbeeld 1.
2. Zie Voorbeeld 1.
3. `a` kan zijn: een drievoud `a = 3n`, één meer dan een drievoud `a = 3n + 1`, of twee meer dan een drievoud `a = 3n + 2`.
  Als `a = 3n`, dan is `a^3 = (3n)^3 = 27n^3 = 3 * 9n^3` ook een drievoud.
  Als `a = 3n + 1`, dan is `a^3 = (3n + 1)^3 = 27n^3 + 27n^2 + 9n + 1 = 3 * (9n^3 + 9n^2 + 3n) + 1` geen drievoud.
  Als `a = 3n + 2`, dan is `a^3 = (3n + 2)^3 = 27n^3 + 54n^2 + 36n + 8 = 3 * (9n^3 + 18n^2 + 12n + 2) + 2` geen drievoud.
  Dus `a^3` kan alleen een drievoud zijn als `a` dat is. Q.e.d.
1. `n` is deelbaar door 12, dan `n = 12 * p = 3 * 4 * p` en dus ook deelbaar door zowel 3 als 4.
2. `n` is deelbaar door 3 en 4, dan `n = 4 * 3 * q = 12 * q` dus ook deelbaar door 12.
3. `n` is deelbaar door 12 `hArr` `n` is deelbaar door 3 en 4.
4. `n` is deelbaar door 12, dan `n = 12 * p = 2 * 6 * p` en dus ook deelbaar door zowel 2 als 6.
5. `n` is deelbaar door 2 en 6 levert een probleem op omdat 6 al deelbaar is door 2. Bijvoorbeeld het getal 18 is deelbaar door 6 en door 2, maar niet door 12.
6. `n` is deelbaar door `a * b` `hArr` `n` is deelbaar door `a` en `b` en GGD(`a,b`) = 1 (ofwel `a` en `b` hebben geen gemeenschappelijke delers behalve 1).
1. Omdat je er van uit gaat dat de stelling niet waar is en dan aantoont dat dit niet kan kloppen omdat er een tegenspraak ontstaat.
2. Neem aan dat de stelling niet waar is. Er bestaat dan een getal `p` dat niet is te schrijven als het product van priemgetallen. Omdat `p` zelf niet piem is, heeft `p` delers, bijvoorbeeld `p = a * b`. Voor die getallen `a` en `b` geldt nu dan minstens één van beide niet priem mag zijn, bijvoorbeeld `b`, dus `b = c * d`. Voor die getallen `c` en `d` geldt nu dan minstens één van beide niet priem mag zijn, bijvoorbeeld `d`, dus `d = e * f`. Etcetera...
  Dit proces moet echter na een eindig aantal stappen beëndigen omdat `p` een eindig getal is. In dat geval bestaat `p` echter uit een product van alleen priemgetallen en dat is in strijd met de aanname dat de stelling niet waar is.
1. Als de stelling niet waar is, dan zit er in elk 0 of 1 duiven. In totaal zijn er dan maximaal `9 xx 1 = 9` duiven in de hokken geplaatst en dat klopt niet met de aanname dat er 10 duiven in de hokken zitten.
2. Als er `n` duiven verdeeld moeten worden over `m` hokken, waarbij `n > m`, dan is er zeker één hok waarin minstens twee duiven zitten.
3. Je kunt maximaal vier getallen kiezen onder de vijf. Je kiest er derhalve altijd minstens twee uit 5, 6, 7, 8, 9, 10. Welke twee je daarvan ook kiest altijd is hun som minstens 11.
4. Het aantal andere mensen dat een ieder kent is een getal uit de serie 1, 2, 3, ..., 49. Omdat er maar 49 van die getallen zijn en 50 personen precies één zo'n getal krijgen, is er altijd minstens één getal bij dat bij twee personen terecht komt.
1. `140 = 2^2 * 5 * 7` en `504 = 2^3 * 3^2 * 7` dus GGD(140,504) = `2^2 * 7 = 28`.
2. `143 = 11 * 13` en `2541 = 3 * 7 * 11^2` dus GGD(143,2541) = 11.
3. GGD(`a,0) = a`.
4. Stel GGD(`a,b) = p`, dan is `a - q*b = c*p - q*d*p = r` waarbij `c` en `q*d` geen gemeenschappelijke deler kunnen hebben, om dat dan `p` niet de GGD van `a` en `b` was. Dus hebben `r = c*p - q*d*p` en `b = q * d * p` ook `p` als grootste gemeenschappelijke deler.
5. `504 = 3 * 140 + 84` dus GGD(140,504) = GGD(140,84)
  `140 = 1 * 84 + 56` dus GGD(14,84) = GGD(84,56)
  `84 = 1 * 56 + 28` dus GGD(84,56) = GGD(56,28)
  `56 = 2 * 28 + 0` dus GGD(56,28) = GGD(28,0) = 28.
  Conclusie GGD(140,504) = 28.
6. Ga na, dat je vindt: GGD(143,2541) = 11.
7. `220 = 5 * 39 + 25` dus GGD(220,39) = GGD(39,25)
  `39 = 1 * 25 + 14` dus GGD(39,25) = GGD(25,14)
  `25 = 1 * 14 + 11` dus GGD(25,14) = GGD(14,11)
  `14 = 1 * 11 + 3` dus GGD(14,11) = GGD(11,3)
  `11 = 3 * 3 + 2` dus GGD(11,3) = GGD(3,2)
  `3 = 1 * 2 + 1` dus GGD(3,2) = GGD(2,1) = 1
  Nu is `1 = 3 - 1 * 2 = 3 - (11 - 3 * 3) = 14 - 4 * 3 - 11 = 4 * (14 - 1 * 11) - 11 = 4 * 14 - 5 * 11 = 4 * 14 - 5 * (25 - 1 * 14) = 9 * 14 - 5 * 25 = 9 * (39 - 1 * 25) - 5 * 25 = 9 * 39 - 14 * 25 = 9 * 39 - 14 * (220 - 5 * 39) = 79 * 39 - 14 * 220`. Je moet dus 79 sprongen van 39 maken en dan 14 sprongen van 220 terug.
`(n^3 - n)^2 = n^2 (n - 1)^2 (n + 1)^2`.
Omdat `n - 1`, `n` en `n + 1` drie opeenvolgende getallen zijn is één van deze drie een drievoud. Omdat je deze factor kwadrateert is het geheel deelbaar door 9.
1. Even en oneven wisselen elkaar af en de drievouden zitten om de drie getallen.
2. `n^5 - n = n(n-1)(n+1)(n^2+1)`
  Je hebt nu voor `n` de volgende vijf mogelijkheden: `n = 5k`, `n = 5k + 1`, `n = 5k + 2`, `n = 5k + 3` of `n = 5k + 4`.
  Als `n = 5k`, dan is `n^5 - n = 5k(5k - 1)(5k + 1)(25k^2 + 1)`, dus `n^5 - n` is deelbaar door 5 en ook door 2 en 3 (drie opeenvolgende getallen), dus deelbaar door `5 * 3 * 2 = 30`.
  Als `n = 5k + 1` dan is `n^5 - n = (5k + 1) * 5k * (5k+2)((5k+1)^2 + 1)`, dus `n^5 - n` is deelbaar door 5 en ook door 2 en 3 (drie opeenvolgende getallen), dus deelbaar door `5 * 3 * 2 = 30`.
  Enzovoorts.
Het aantal keren dat je `n` optelt is ook variabel, namelijk precies `n` keer. Daarom moet je de productregel gebruiken voor `f`(`n`)` = n * n`.
1. KGV(5,7) = 35 en KGV(10,15) = 30.
2. `140 = 2^2 * 5 * 7` en `504 = 2^3 * 3^2 * 7` dus KGV(140,504) = `2^3 * 3^2 * 5 * 7 = 2520`.
3. KGV(`p,q`) `= p * q` als `p` en `q` priem zijn.
4. Stel GGD(`a,b`) `= u`, dan is `a = p * u` en `b = q * u` waarin `p` en `q` geen gemene delers hebben. Nu is: `a * b = p * u * q * u = p * q * u^2`. Ook is: KGV(`a,b`) = KGV(`pu,qu`) = `p * q * u` (want `p` en `q` hebben geen gemene delers). Dus is KGV(`a,b) = a * b // u`.
Als `a = 2n + 1` dan is `a^3 = 8n^3 + 12n^2 + 6n + 1 = 2(4n^3 + 6n^2 + 3n) + 1` dus ook oneven.
Als `a^3` is oneven dan zijn er twee mogelijkheden: `a` is even of `a` in oneven. En `a` is even klopt niet want dan moet ook `a^3` even zijn.
1. GGD(33,91) = 1
2. KGV(33,91) = 3003
3. Algoritme van Euklides: `1 = 4 * 91 - 11 * 33`, dus 4 sprongen van 91 naar rechts en 11 van 33 naar links.
Neem bijvoorbeeld `g = a*10^3 + b*10^2 + c*10 + d` dan is `a+b+c+d` een drievoud.
En dan is `g = 999a + 99b + 9c + a + b + c + d` ook een drievoud.
Dit kun je gemakkelijk uitbreiden naar grotere en kleinere getallen. Je gebruikt steeds het tientallig stelsel.