title: Chinese reststelling
text: In de getaltheorie, een deelgebied van de wiskunde, bepaalt de Chinese reststelling een getal  dat voor elk van een aantal gegeven delers die onderling relatief priem zijn, bij deling daardoor een gegeven rest achterlaat.
  
  Meer formeel zegt de stelling dat een stelsel congruentievergelijkingen in het gehele getal :
  
  voor delers  die relatief priem zijn, een oplossing heeft. De stelling geeft ook aan hoe de oplossing gevonden kan worden.
  
  Wat is bijvoorbeeld het kleinste getal  dat bij deling door 3 een rest 2 heeft, bij deling door 5 een rest 3 en ten slotte bij deling door 7 een rest 2 heeft? Het antwoord is 23.
  
  Geschiedenis 
  De stelling werd voor het eerst beschreven in de vierde eeuw na Chr. door Sunzi 孫子 in zijn Sunzi Suanjing 孫子算經, het 'rekenkundig handboek van Meester Sun'. De stelling werd opnieuw in 1247 gepubliceerd, nu door Qin Jiushao, in zijn Wiskundige verhandeling in negen secties. Beiden waren wiskundige uit de tijd van het Chinese Keizerrijk, dat duurde van 221 v.Chr. tot 1911.
  
  Principe 
  Laat  positieve gehele getallen zijn die paarsgewijs relatief priem zijn, wat wil zeggen dat de grootste gemene deler van ieder tweetal daarvan 1 is. Dan is er voor elk -tal gehele getallen  een geheel getal  dat een oplossing is van het stelsel van simultane congruenties: 
   
  
  Alle oplossingen  zijn congruent modulo het kleinste gemene veelvoud van de .
  
  Een oplossing  wordt gevonden door steeds twee congruenties tot een congruentie samen te voegen.
  
  waarin  en  relatief priem zijn.
  
  Er zijn dan volgens de stelling van Bachet-Bézout twee gehele getallen  en  zodat 
  .
  Hierin kunnen  en  met het uitgebreide algoritme van Euclides worden berekend. Er is dus een oplossing . Inderdaad is
  , 
  
  waaruit volgt dat 
  
  Evenzo is 
  ,
  
  waaruit volgt dat 
  
  Dit geeft samen de nieuwe congruentie 
  
  Het stelsel van  congruenties is hierdoor gereduceerd tot een stelsel van  congruenties. Er kan zo worden doorgegaan totdat er een  is gevonden die aan de  oorspronkelijke congruenties voldoet.
  
  Merk op dat sommige van deze stelsels zelfs een  oplossing hebben als de getallen  niet paarsgewijs relatief priem zijn. Het exacte criterium is: er bestaat een oplossing  dan en slechts dan als  voor alle  en .
  
  Voorbeeld 
  Gezocht wordt een geheel getal  waarvoor geldt dat 
   
  
  Begin met de eerste twee congruenties. Er zijn getallen  en , zodat . Hoewel een oplossing voor deze vergelijking meteen is te zien, geeft ook het uitgebreide algoritme van Euclides de oplossing  en . Het getal  voldoet dus aan de eerste twee congruenties en geeft de nieuwe congruentie:
  
  Gecombineerd met
  
  leidt dit tot het bestaan van nieuwe getallen  en  die voldoen aan . Het uitgebreide algoritme van Euclides geeft  en . Dus voldoet  aan beide congruenties, en daarmee aan de drie gegeven congruenties. Een andere oplossing is bijvoorbeeld . Het algoritme kost veel rekentijd.
  
  Getaltheorie
  Modulair rekenen