Lineaariset kongruenssiryhmät
Hirsimäki, Mona (2020)
2020
Matematiikan ja tilastotieteen kandidaattiohjelma - Bachelor's Programme in Mathematics and Statistics
Informaatioteknologian ja viestinnän tiedekunta - Faculty of Information Technology and Communication Sciences
This publication is copyrighted. You may download, display and print it for Your own personal use. Commercial use is prohibited.
Hyväksymispäivämäärä
2020-12-15
Julkaisun pysyvä osoite on
https://urn.fi/URN:NBN:fi:tuni-202012158858
https://urn.fi/URN:NBN:fi:tuni-202012158858
Tiivistelmä
Tämän tutkielman tarkoituksena on esitellä lineaaristen kongruenssiryhmien ratkaisumenetelmiä, kun muuttujien ja kongruenssien lukumäärät vaihtelevat. Kongruenssien modulien arvoilla on myös vaikutusta ratkaisutapaan. Tutkielma nojaa kirjallisuuteen ja päälähdeteoksena käytetään Rosenin kirjaa Elementary Number Theory and its Applications.
Tutkielma kuuluu pääasiassa matematiikassa lukuteorian osa-alueeseen. Keskeisiä tutkielman käsitteitä ovat muun muassa jaollisuus, kongruenssi ja suurin yhteinen tekijä. Lukijalta oletetaankin osaamista lukuteorian alkeista, vaikka joitakin tärkeimpiä perusasioita esitetään tutkielman alussa. Tutkielma kuuluu myös matematiikassa lineaarialgebran osa-alueeseen, koska kongruenssiryhmä muodostuu kongruenssiyhtälöistä, ja siksi lineaarisen yhtälöryhmän käsitteen ymmärtäminen on tärkeää. Lukijan oletetaan myös hallitsevan matriisilaskennan perusteet.
Tutkielmassa esitetään ensin yhden muuttujan ja kahden kongruenssin muodostaman lineaarisen kongruenssiryhmän ratkaisumenetelmä. Kongruenssien modulien ei tarvitse olla sama positiivinen kokonaisluku. Tulokseksi saadaan, että jos kongruenssiryhmä on ratkeava, niin ratkaisu on yksikäsitteinen modulo pyj(m, n), missä m ja n ovat kongruenssien modulit.
Toiseksi esitetään kahden muuttujan ja kahden kongruenssin muodostaman lineaarisen kongruenssiryhmän kaksi eri ratkaisumenetelmää. Tässä kongruenssiryhmässä kongruenssien modulien on oltava sama positiivinen kokonaisluku. Ensin esitetään yksinkertainen eliminointimenetelmä, jossa tarkoituksena on eliminoida toinen kongruenssiryhmän muuttujista. Ratkaistun muuttujan arvo sijoitetaan toiseen alkuperäiseen kongruenssiryhmän kongruenssiyhtälöön, jolloin saadaan myös toisen muuttujan arvo. Toisen ratkaisumenetelmän avulla saadaan selvitettyä sekä lineaarisen kongruenssiryhmän ratkeavuus että ratkai- sun muoto, jos se on olemassa. Jos ratkaisu on olemassa, se on yksikäsitteinen modulo m.
Viimeisessä luvussa esitellään, miten matriiseja voidaan esittää kongruenssimuodossa ja miten matriisimerkintöjä käyttäen voidaan ratkaista suuriakin lineaarisia kongruenssiryhmiä. Määritelmien ja lauseiden perusteella saadaan johdettua tulos, että kongruenssi X ≡ Aˆ(−1)B (mod m) antaa ratkaisumenetel- män ratkaista lineaarinen kongruenssiryhmä.
Tutkielma kuuluu pääasiassa matematiikassa lukuteorian osa-alueeseen. Keskeisiä tutkielman käsitteitä ovat muun muassa jaollisuus, kongruenssi ja suurin yhteinen tekijä. Lukijalta oletetaankin osaamista lukuteorian alkeista, vaikka joitakin tärkeimpiä perusasioita esitetään tutkielman alussa. Tutkielma kuuluu myös matematiikassa lineaarialgebran osa-alueeseen, koska kongruenssiryhmä muodostuu kongruenssiyhtälöistä, ja siksi lineaarisen yhtälöryhmän käsitteen ymmärtäminen on tärkeää. Lukijan oletetaan myös hallitsevan matriisilaskennan perusteet.
Tutkielmassa esitetään ensin yhden muuttujan ja kahden kongruenssin muodostaman lineaarisen kongruenssiryhmän ratkaisumenetelmä. Kongruenssien modulien ei tarvitse olla sama positiivinen kokonaisluku. Tulokseksi saadaan, että jos kongruenssiryhmä on ratkeava, niin ratkaisu on yksikäsitteinen modulo pyj(m, n), missä m ja n ovat kongruenssien modulit.
Toiseksi esitetään kahden muuttujan ja kahden kongruenssin muodostaman lineaarisen kongruenssiryhmän kaksi eri ratkaisumenetelmää. Tässä kongruenssiryhmässä kongruenssien modulien on oltava sama positiivinen kokonaisluku. Ensin esitetään yksinkertainen eliminointimenetelmä, jossa tarkoituksena on eliminoida toinen kongruenssiryhmän muuttujista. Ratkaistun muuttujan arvo sijoitetaan toiseen alkuperäiseen kongruenssiryhmän kongruenssiyhtälöön, jolloin saadaan myös toisen muuttujan arvo. Toisen ratkaisumenetelmän avulla saadaan selvitettyä sekä lineaarisen kongruenssiryhmän ratkeavuus että ratkai- sun muoto, jos se on olemassa. Jos ratkaisu on olemassa, se on yksikäsitteinen modulo m.
Viimeisessä luvussa esitellään, miten matriiseja voidaan esittää kongruenssimuodossa ja miten matriisimerkintöjä käyttäen voidaan ratkaista suuriakin lineaarisia kongruenssiryhmiä. Määritelmien ja lauseiden perusteella saadaan johdettua tulos, että kongruenssi X ≡ Aˆ(−1)B (mod m) antaa ratkaisumenetel- män ratkaista lineaarinen kongruenssiryhmä.
Kokoelmat
- Kandidaatintutkielmat [8996]