Siterer en oppgave gitt av det danske laget i Baltic Way:
Hilmar har til et rave party købt masser af øl, og da han tæller hvor mange
han har, opdager han at antallet er et primtal. Han fordeler så mange af øllene som muligt på 60 fade med lige mange på hvert. Han konstaterer derefter at han har mere end én tilbage, og at antallet af tiloversblevne øl ikke er et primtal.
Hvor mange øl har Hilmar til overs?
Hvor stor rest?
Moderatorer: Vektormannen, espen180, Aleks855, Solar Plexsus, Gustav, Nebuchadnezzar, Janhaa
La p være antallet øl Hilmar kjøpte. Vi vil da finne p (mod 60). Siden [tex]60=2^2 \cdot 3 \cdot 5[/tex] finner vi først ut hvilke restklasser primtallene kan tilhøre modulo 3, 4 og 5. Modulo 3 er alle primtall 1 eller 2, modulo 4 er alle primtall 1 eller 3, og modulo 5 er primtall ikke null. (Strengt tatt finnes spesialtilfellene 2, 3 og 5, men p kan ikke være noen av disse, da p (mod 60) da ville vært et primtall.) Altså har vi av det kinesiske restteoremet 16 muligheter for hva primtall (unntatt 2, 3, 5) kan være modulo 60. De kan vi enten regne ut ved å sette opp de 16 mulige kongruenssystemene og løse dem, eller prøve primtallene etter tur til vi har funnet 16 mulige verdier. Vi kan også bare skrive opp tallene mellom 0 og 60 og fjerne alle som er delelige med 2, 3 eller 5. Uansett får vi at primtall modulo 60 (unntatt 2, 3 og 5) enten er 1, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 49, 53 og 59. Da antallet øl til overs er større enn 1 kan vi utelukke 1, og ellers er alle de andre restene primtall unntatt 49. Altså har Hilmar 49 øl til overs. (Han må forøvrig minst ha kjøpt 109 øl, og kan altså vente seg et heidundranes rave party.)