SNY har ordet

Kursen följer i huvudsak två spår, varvid studenterna har rätt stor frihet att välja det ena eller vikta ihop dem (spåren korsar för övrigt varandra). Det ena är diofantiska ekvationer, algebraiska ekvationer vilkas heltalslösningar efterfrågas. Bland annat utreds vilka primtal som kan skrivas på formen x² + ny², där n = 1,2,3, plus en del andra fall i form av inlämningsuppgifter. För en annan klassisk typ, Pells ekvation, x² - Dy² = 1$ (där D inte är en jämn kvadrat) ges en (programmerbar) algoritm, kedjebråksutveckling. Det senare snuddar också vid en klassisk algoritm för faktorisering av hyfsat stora tal. Det är det andra spåret; primtalstest och faktorisering. Den teori som alla läser ger den nödvändiga bakgrunden, men inslaget är valfritt.

Innehåll

Primtal, moduloaritmetik, Fermats lilla sats, primitiva rötter, kinesiska restsatsen, kvadratiska rester, reciprocitet. Summor av kvadrater. Kedjebråk.

Mål

Kursen ska ge insikt i elementära talteoretiska begrepp och förmåga att använda dem. Efter fullgjord kurs skall du

• ha kunskap om heltalens uppbyggnad med hjälp av primtal och om primtalens fördelning,
• kunna räkna med kongruenser och kunna lösa vissa diofantiska ekvationer,
• känna till viktiga talteoretiska funktioner som t.ex. Eulers phi-funktion och dessas användning,
• känna till och kunna tillämpa Möbius inversionsformel,
• ha kännedom om vissa enkla primalitetstest,
• kunna kvadratiska reciprocitetssatsen,
• kunna räkna med kedjebråk och använda sådana för att lösa Pells ekvation,
• kunna hantera de Gaussiska heltalen och känna till hur dessa används för att skriva heltal som summor av två kvadrater.

Examinationsmoment

TEN1 - 6,0 HP
Skriftlig tentamen (U,3,4,5)

Organisation

Föreläsningar

Litteratur

K.H. Rosen: Elementary Number Theory and its Applications. 6th ed., Addison-Wesley.

Rekommenderade förkunskaper

Grundbegrepp i diskret matematik

Diskret matematik TATA32 - 8,0 HP - HT1 block 2, HT2 block 3

Kommentarer

Logga in för att kunna läsa och skriva kommentarer.