Potpuni i smanjeni sustavi odbitaka. Predavanja iz teorije brojeva. Vježbe za samostalan rad

Skup brojeva usporediv s a modulo m nazvao klasa brojeva modulo m(ili klasa ekvivalencije). Svi brojevi jedne klase imaju oblik mt+ r na fiksnom r.

Za dano m, r može poprimiti vrijednosti od 0 do m-1, tj. sve postoji m klase brojeva po modulu m, a svaki cijeli broj će pasti u jednu od modulo klasa m. dakle,

Z= m m … [m-1]m, Gdje [ r]m={x Z: x≡r(mod m)}

Bilo koji broj klasa [ r]m nazvao minus modulo m u odnosu na sve brojeve iste klase. Broj jednak ostatku r, nazvao najmanji nenegativni odbitak.

Odbitak koji je najmanji u apsolutnoj vrijednosti naziva se apsolutno najmanji odbitak.

Primjer

Uzmimo modul m=5. I neka a=8. Podijelimo se a na m sa ostatkom:

Ostatak r=3. To znači 8 5, a najmanji nenegativan ostatak broja 8 modulo 5 je 3.

Najmanji apsolutni odbitak može se pronaći izračunavanjem r-m=3-5=-2 i usporedbom apsolutnih vrijednosti |-2| i |3|. |-2|<|3|, значит -2 – абсолютно наименьший вычет числа 8 по модулю 5.

Uzimajući jedan odbitak od svake klase, dobivamo puni sustav odbitaka modulo m. Ako su svi ti brojevi najmanji nenegativni modulo ostaci m, tada se takav sustav odbitaka naziva potpuni sustav najmanje nenegativnih ostataka, a označava se sa Z m.

{0; 1;…; m-1) = Z m– cjelovit sustav najmanje nenegativnih ostataka.

(– ;…; 0;…; ) (ako m– neparan broj);

( - ,…,-1, 0, 1,…, ) ili (- ,…, -1, 0, 1,…, ) (ako m paran broj) je potpuni sustav apsolutno najmanjih ostataka.

Primjer

Ako m=11, tada je potpuni sustav najmanje nenegativnih ostataka (0; 1; 2; 3; 4; 5; 6; 7; 8; 9; 10), a potpuni sustav apsolutno najmanjih ostataka je (–5 ; – 2;

Izjava 1

Bilo koje m brojevi koji su u paru neusporedivi po modulu m tvore potpuni sustav ostataka za ovaj modul.

Dokaz:

Doista, zbog neusporedivosti, ti brojevi pripadaju različitim klasama, a budući da njihov m komada, tada svaka postojeća klasa sadrži točno jedan broj.

Izjava 2

Ako ( a, m) = 1, i x prolazi kroz cijeli sustav modulo ostataka m, To sjekira+b, Gdje b– bilo koji broj iz Z također prolazi kroz cijeli sustav modulo ostataka m.

Dokaz:

Brojke sjekira+b bit će glatka m stvari. Ostaje dokazati da bilo koja 2 broja sjekira 1 +b I sjekira 2 +b neusporediv po modulu m, Ako x 1 x 2 (mod m)

Dokaz kontradikcijom. Pretpostavimo da sjekira 1 +b≡ sjekira 2 +b(mod m) zbog 4. svetinja usporedbi, sjekira 1 ≡ sjekira 2 (mod m) zbog prirode usporedbi br. 9 i činjenice da ( a, m) = 1, imamo x 1 ≡ x 2 (mod m). Dobili smo kontradikciju s činjenicom da x 1 x 2 (mod m). Stoga je pretpostavka netočna, što znači da je suprotno istinito. To jest sjekira 1 +b I sjekira 2 +b neusporediv po modulu m, Ako x 1 x 2 (mod m), što je trebalo i dokazati.

Obično kao potpuni sustav odbitaka po modulu m uzimaju se najmanji nenegativni ostaci

0,1,...,m − 1

ili apsolutno najmanji odbici koji se sastoje od brojeva

,

u slučaju ak m i brojevima

u slučaju čak m .

Vidi također

Književnost

• I. M. Vinogradov Osnove teorije brojeva. - M.-L.: Država. izd. tehnička i teorijska literatura, 1952. - 180 str.

Zaklada Wikimedia.

2010.

Pogledajte što je "Puni sustav odbitaka" u drugim rječnicima:

Modulo m, bilo koja zbirka cijelih brojeva koja sadrži jedan broj iz svake klase brojeva po modulu m (dva cijela broja a i b pripadaju istoj klasi po modulu m ako je a b djeljiv s m; vidi Redukcija). Kao P. s. V. češće…… Modulo je bilo koji skup cijelih brojeva koji su međusobno neusporedivi modulo. Obično kao P. s. V. modulo najmanjih nenegativnih ostataka 0, 1, . . ., m 1 ili apsolutno najmanji ostaci, koji se sastoje od brojeva 0, +1, . . ., V… …

Matematička enciklopedija Dio potpunog sustava ostataka (vidi Cjeloviti sustav ostataka), koji se sastoji od brojeva koji su prosti s modulom m. p.s. V. sadrži φ(m) brojeva [φ(m) broj brojeva koji su prosti s m i manji su od m]. Bilo koji φ(m) brojevi koji nisu usporedivi po modulu m i... ...

Velika sovjetska enciklopedija

Usporedba po modulu prirodnog broja n u teoriji brojeva je relacija ekvivalencije na prstenu cijelih brojeva povezanih s djeljivošću s n. Faktorski prsten u ovoj relaciji naziva se prsten ostataka. Skup odgovarajućih identiteta i... ... Wikipedije

U teoriji brojeva, usporedba [razjasniti] modulo prirodnog broja n, relacija ekvivalencije na skupu cijelih brojeva specificiranih označenim brojem, povezana s djeljivošću njime. Faktorski prostor u ovoj relaciji naziva se “prsten” ... ... Wikipedia

Simetrija snježne pahulje povezana je s grupom rotacija za kut koji je višekratnik od 60°. Konačna grupa je algebarska grupa koja sadrži konačan broj elemenata (taj se broj naziva njezin red). Nadalje, pretpostavlja se da je grupa multiplikativna, odnosno operacija u ... ... Wikipediji Modulo je bilo koji skup cijelih brojeva koji su međusobno neusporedivi modulo. Obično kao P. s. V. modulo najmanjih nenegativnih ostataka 0, 1, . . ., m 1 ili apsolutno najmanji ostaci, koji se sastoje od brojeva 0, +1, . . ., V… …

I Sadržaj: I. Pučka pučka nastava uopće. II. Osnovno javno obrazovanje u inozemstvu: Austro-Ugarska, Engleska, Belgija, Bugarska, Njemačka, Nizozemska, Danska, Španjolska, Italija, Norveška, Portugal, Rumunjska, Srbija, ... ... Enciklopedijski rječnik F.A. Brockhaus i I.A. Ephron

- - rođen 26. svibnja 1799. u Moskvi, u Nemetskoj ulici u kući Skvorcova; preminuo 29. siječnja 1837. u Petrogradu. Puškin je s očeve strane pripadao staroj plemićkoj obitelji koja je, prema genealogijama, potjecala od potomka "iz ... ... Velika biografska enciklopedija

Skup zatvorenih formula predikatske logike 1. stupnja. E. t. Th(K) algebarski sustavi potpisa tzv. skup svih zatvorenih formula logike predikata 1. stupnja signature istinit na svim sustavima iz klase K. Ako klasa... ... Modulo je bilo koji skup cijelih brojeva koji su međusobno neusporedivi modulo. Obično kao P. s. V. modulo najmanjih nenegativnih ostataka 0, 1, . . ., m 1 ili apsolutno najmanji ostaci, koji se sastoje od brojeva 0, +1, . . ., V… …

ili bilo koji uzastopni str brojevima.

Ovaj sustav se zove potpuni sustav brojeva neusporediv po modulu str ili cjelovit sustav modulo odbitaka str. Očito, svakakve str uzastopni brojevi tvore takav sustav.

Svi brojevi koji pripadaju istoj klasi imaju mnogo zajedničkih svojstava, stoga se u odnosu na modul mogu smatrati jednim brojem. Svaki broj uključen u usporedbu kao zbroj ili faktor može se, bez narušavanja usporedbe, zamijeniti s njim usporedivim brojem, tj. s brojem koji pripada istoj klasi.

Drugi element koji je zajednički svim brojevima dane klase je najveći zajednički djelitelj svakog elementa te klase i modula str.

Neka a I b usporedivi po modulu str, Zatim

Teorema 1. Ako u sjekira+b umjesto x zamijenimo sve redom strčlanovi cjelovitog brojevnog sustava

Stoga svi brojevi sjekira+b, Gdje x=1,2,...str-1 nisu usporedivi po modulu str(inače, brojevi 1,2,... str-1 bio bi usporediv u modulu str.

Bilješke

1) U ovom članku riječ broj podrazumijevat će se kao cijeli broj.

Književnost

• 1. K. Ireland, M. Rosen. Klasičan uvod u modernu teoriju brojeva − M: Mir, 1987.
• 2. G. Davenport. Viša aritmetika − M: Nauka, 1965.
• 3. P.G. Lejeunea Dirichleta. Predavanja iz teorije brojeva. − Moskva, 1936.

Prema svojstvu usporedbi br. 15, brojevi iste klase modulo m imati s modulom m isti GCD. Posebno su važni razredi za koje je jednak 1.

Uzimajući jedan broj iz svake od ovih klasa, dobivamo smanjeni sustav odbitaka modulo m. Obično je izoliran iz sustava najmanje nenegativnih modulo ostataka m.

Reducirani sustav najmanjih nenegativnih modulo ostataka m označeno sa U m.

Broj brojeva u zadanom modulo sustavu ostataka m, očito je jednak φ( m).

Primjer:

Zadani sustav odbitaka po modulu 15 je (1; 2; 4; 7; 8; 11; 13; 14). Uočimo da je φ(15)=(5–1)∙(3–1)= 8 i doista, u zadanom sustavu ostataka po modulu 15 postoji točno 8 elemenata.

Izjava 1

Bilo koji φ( m) brojevi koji su u parovima neusporedivi po modulu m i međusobno prime sa m tvore reducirani sustav ostataka.

(Dokaz je očit kao u tvrdnji 1, točka 2)

Izjava 2

Ako ( a, m) = 1, x prolazi kroz reducirani sustav modulo ostataka m, To sjekira također prolazi kroz reducirani sustav modulo ostataka m. (Dokaz je očit kao u tvrdnji 2, točka 2).

Obrnuti element.

Kažu da je element b nazvao obrnuti Do a modulo m, Ako a∙b≡1(mod m), i napiši b ≡ a–1 (mod m).

Općenito, klasična teorija brojeva ne treba takav koncept kao inverzni element, kao što se može vidjeti čitajući, na primjer, . Međutim, kriptologija koristi sustave ostataka iu teoretskom iu algebarskom aspektu, te stoga, radi lakšeg predstavljanja algebarskih temelja kriptologije, uvodimo koncept inverznog elementa.

Postavlja se pitanje: vrijedi li to za sve elemente u ovom modulu? m postoji inverz (množenjem), a ako za neke elemente inverz postoji, kako ga pronaći?

Za odgovor na ovo pitanje koristit ćemo se proširenim Euklidovim algoritmom. Razmotrimo prvo međusobno proste brojeve a i modul m. Onda očito ( a,m)=1. Prošireni euklidski algoritam omogućuje dobivanje brojeva x I g, tako da sjekira+moja=(a,m), ili, što je isto, sjekira+moja=1. Iz zadnjeg izraza dobivamo usporedbu sjekira+moja≡1(mod m). Jer moj≡0(mod m), To sjekira≡1(mod m), što znači broj dobiven korištenjem proširenog Euklidovog algoritma x je upravo traženi inverzni element broju a modulo m.

Primjer.

a=5, m=7. Treba pronaći a-1 mod m.

Upotrijebimo prošireni Euklidov algoritam.

Naličje:

1=5–2∙2=5–(7–5∙1)∙2=5∙3–7∙2.

x=3, g=–2.

5 -1 ≡3 (mod 7)

Provjera: 5∙3=15. 15≡1 (mod 7).

Doista, 3 je inverz od 5 modulo 7.

Dakle, konstruktivno smo potvrdili da za brojeve koji su prosti s modulom, postoji inverz u odnosu na ovaj modul. Postoje li inverzni elementi za brojeve koji nisu međusobno prosti sa svojim modulom?

Neka ( a,m)=d≠1. Tada se a i m mogu prikazati u obliku a=d∙a 1 , m=d∙m 1. Pretpostavimo da za a postoji inverzni element po modulu m, tj b: a∙b≡1(mod m). Zatim a∙b= m∙k+1. Ili, što je isto, d∙a 1 ∙b= d∙m 1 ∙k+1. Ali tada, prema teoremu 2 iz §1 str.1, zbog činjenice da su i lijeva strana ove jednadžbe i prvi član na desnoj strani podijeljeni na d, To d\1, ali to nije istina, jer d≠1. Došli smo do kontradikcije, stoga je pretpostavka o postojanju inverznog elementa netočna.

Dakle, upravo smo dokazali

Teorem reverzibilnosti

a-1 (mod m) (a, m) = 1.

Sažimajući sva obrazloženja ove točke, možemo reći da su samo brojevi koji su relativno prosti s modulom invertibilni, a njihovi inverzi se mogu pronaći pomoću proširenog Euklidovog algoritma.

OSNOVNI PODACI IZ TEORIJE

6. 1. Definicija 1.

Klasa brojeva po modulu m je skup svih onih i samo onih cijelih brojeva koji, kada se dijele s m, imaju isti ostatak r, odnosno usporediv po modulu m (m Î N, t> 1).

Označavanje klase brojeva koji imaju ostatak r: .

Svaki broj iz razreda naziva se ostatak po modulu m, a sama klasa naziva se klasa ostataka po modulu m.

6. 2. Svojstva skupa modulo klasa ostataka T:

1) ukupni modulo T htjeti T klase odbitaka: Z t = { , , , … , };

2) svaka klasa sadrži beskonačan skup cijelih brojeva (ostataka) oblika: = ( a= mq+ r/qÎ Z, 0£ r< m}

3) "AÎ : Aº r(mod m);

4) "a, bÎ : Aº b(mod m), to jest bilo koja dva uzeta ostatka od jednog razred, usporediv modulo T;

5) "AÎ , " bÎ : A b(mod m), odnosno nema dva odbitka; uzeti iz različitih razredi, neusporediv modulo T.

6. 3. Definicija 3.

Kompletan sustav ostataka po modulu m je bilo koji skup od m brojeva uzet jedan i samo jedan iz svake klase ostataka po modulu m.

Primjer: Ako m= 5, tada je (10, 6, – 3, 28, 44) potpuni sustav ostataka po modulu 5 (i ne jedini!)

Posebno,

skup (0, 1, 2, 3, … , m–1) je sustav najmanje nenegativan odbici;

set (1, 2, 3, … , m –1, T) je sustav najmanje pozitivno odbici.

6. 4. Napomena:

Ako ( X 1 , X 2 , … , x t) – potpuni sustav odbitaka po modulu T, To

.

6. 5. Teorem 1.

Ako {X 1 , X 2 , … , x t} – potpuni sustav odbitaka po modulu t, "a, bÎ Z i(a, t) = 1, – zatim brojevni sustav {Oh 1 +b, Oh 2 + b, … , ah t+b} također tvori potpuni sustav ostataka modulo t .

6. 6. Teorem 2.

Svi ostaci iste klase ostataka po modulu m imaju isti najveći zajednički djelitelj s brojem m: "a, bÎ Þ ( A; T) = (b; T).

6. 7. Definicija 4.

Klasa odbitka za dani modulo m se kaže da je međusobno prost s modulom m,ako je barem jedan ostatak ove klase koprost s tzv.

Imajte na umu da u ovom slučaju, prema teoremu 2 Sve brojevi ove klase bit će koprosti s modulom T.

6. 8. Definicija 5.

Reducirani sustav ostataka za dani modul m je sustav ostataka uzet jedan i samo jedan iz svake klase koprost s modulom m.

6. 9. Napomena:

1) reducirani sustav modulo ostataka T sadrži j( T) brojevi ( X 1 , X 2 ,…, };

2) : .

3) "x i : (x i, m) = 1;

Primjer : Neka modulo T= 10 postoji 10 klasa odbitaka:

Z 10 = ( , , , , , , , , , ) – skup klasa ostataka po modulu 10. Cjeloviti sustav modificiranih odbitaka 10 će, na primjer, biti ovako: (0, 1, 2, 3, 4, 5, 6, 7, 8, 9).

Mnoge klase ostataka, međusobno prosti s modulom m= 10: ( , , , )(j(10) = 4).

Smanjeni sustav odbitaka modulo 10 će biti, na primjer,

(1, 3, 7, 9), ili (11, 43, – 5, 17), ili ( – 9, 13, – 5, 77), itd. (svugdje j(10) = 4 broja).

6.10. Praktički: sastaviti jedan od mogućih reduciranih sustava ostataka mod m, potrebno je iz cjelovitog sustava ostataka mod m odabrati one rezidue koji su prosti s m. Takvih će brojeva biti j( T).

6.11. Teorem 3.

Ako{X 1 , X 2 ,…, } – reducirani sustav odbitaka po modulu t I

(A, m) = 1, – zatim brojevni sustav {Oh 1 , Oh 2 , … , sjekira j (t)} također oblici

reducirani sustav odbitaka po modulu t .

6.12. Definicija 6.

Iznositi( Å ) dedukcijski razredi I +b, jednako zbroju bilo koja dva odbitka, uzetog po jedan iz svake dane klase i : Å = , Gdje"AÎ , "bÎ .

6.13. Definicija 7.

Rad( Ä ) dedukcijski razredi I modulo m je klasa ostataka , odnosno klasa ostataka koja se sastoji od brojeva a ´ b, jednako umnošku bilo koja dva ostatka, uzetog po jedan iz svake dane klase i : Ä = , Gdje"AÎ , "bÎ .

Dakle, u skupu modulo rezidualnih klasa T: Z t= ( , , ,…, ) definirane su dvije algebarske operacije – “zbrajanje” i “množenje”.

6.14. Teorem 4.

Skup klasa ostataka Z m modulo m je asocijativno-komutativni prsten s identitetom:

< Z t , +, · > = < { , , ,…, }, +, · > – prsten.

TIPIČNI ZADACI

1. Modulo T= 9:

1) potpuni sustav najmanje pozitivnih odbitaka;

2) potpuni sustav najmanje nenegativnih ostataka;

3) proizvoljan cjeloviti sustav odbitaka;

4) cjelovit sustav odbitaka najmanje apsolutne vrijednosti.

Odgovor:1) {1, 2, 3, 4, 5, 6, 7, 8, 9}; 2) {0, 1, 2, 3, 4, 5, 6, 7, 8};

2. Napravite reducirani sustav modulo odbitaka T= 12.

Otopina.

1) Kreirajmo potpuni sustav najmanje pozitivnih ostataka modulo T= 12:

(1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12) (ukupno T= 12 brojeva).

2) Izbrišite iz ovog sustava brojeve koji nisu međusobno prosti s brojem 12:

{1, 2 , 3 , 4 , 5, 6 , 7, 8 , 9 , 10 , 11, 12 }.

3) Preostali brojevi, međusobno prosti s brojem 12, tvore željeni reducirani sustav modulo ostataka T= 12 (ukupno j( T) = j(12) = 4 broja).

Odgovor:(1, 5, 7, 11) – reducirani sustav modulo ostataka T= 12.

130. Napravite 1) potpuni sustav najmanje pozitivnih odbitaka; 2) potpuni sustav najmanje nenegativnih ostataka; 3) proizvoljni sustav odbitaka; 4) cjelovit sustav odbitaka najmanje apsolutne vrijednosti; 5) reducirani sustav odbitaka: a) modulo m= 6; b) po modulu m = 8.

131. Je li skup (9, 2, 16, 20, 27, 39, 46, 85) potpuni sustav ostataka po modulu 8?

132 Po kojem modulu je skup (20, – 4, 22, 18, – 1) potpuni sustav ostataka?

133. Napravite reducirani sustav odbitaka po modulu m, ako a) m= 9; b) m= 24; V) m= 7. Koliko bi brojeva trebao sadržavati takav sustav?

134. Formulirajte osnovna svojstva potpunog sustava ostataka i reduciranog sustava ostataka modulo m .

135. Koji elementi razlikuju reducirani i potpuni sustav najmanje nenegativnih ostataka jednostavno po modulu?

136. Pod kojim su uvjetom brojevi A I - A pripadaju istoj klasi modulo ostataka m?

137. Kojim razredima ostataka po modulu 8 pripadaju svi prosti brojevi? r³ 3 ?

138. Tvori li skup brojeva (0, 2 0, 2 1, 2 2, ..., 2 9) cjelovit sustav ostataka po modulu 11?

139. Koliko klasa ostataka po modulu 21 pripada svim ostacima iz jedne klase ostataka po modulu 7?

140. Skup cijelih brojeva Z rasporediti po razredima ostataka modulo 5. Napraviti tablice zbrajanja i množenja u rezultirajućem skupu razreda ostataka Z 5. Je li set Z 5: a) grupa s operacijom zbrajanja klasa? b) grupa s operacijom množenja klasa?

§ 7. EULEROV TEOREM. Fermatov mali teorem

OSNOVNI PODACI IZ TEORIJE

7. 1. Teorem 1.

Ako aÎ Z,TÎ N, t>1 I(A;T) = 1, – tada u beskonačnom nizu potencija a 1 , A 2 , A 3 , ... , A s , … , A t... postoje najmanje dvije potencije s eksponentima s i t(s<t) takav da . (*)

7. 2. Komentar. Naznačivši t– s = k> 0, iz (*) dobivamo: . Podižući obje strane ove usporedbe na snagu nÎ N, dobivamo: (**). To znači da postoji beskonačan broj potencija broja a, zadovoljavajuća usporedba (**). Ali Kako pronaći ove pokazatelje? Što najmanje pokazatelj koji zadovoljava usporedbu (**) ? Na prvo pitanje je odgovoreno Eulerov teorem(1707 – 1783).

7. 3. Eulerov teorem.

Ako aÎ Z,TÎ N, t>1 I(A;T) = 1, - To . (13)

Primjer. Neka A = 2,T = 21, (A; T) = (2; 21) = 1. Tada je . Kako je j (21) = 12, tada je 2 12 º 1(mod 21). Zaista: 2 12 = 4096 i (4096 – 1) 21. Tada je očito da je 2 24 º 1(mod 21), 2 36 º 1(mod 21) i tako dalje. Ali je li eksponent 12 - najmanji, zadovoljavajuća usporedba 2 nº 1(mod 21) ? Ispostavilo se da nije. Najniži pokazatelj htjeti n= 6: 2 6 º 1(mod 21), jer je 2 6 – 1 = 63, a 63 21. Primijetite da najmanje indikator treba tražiti samo među djeliteljima brojeva j( T) (u ovom primjeru – među djeliteljima broja j(21) = 12).

7. 4. Fermatov mali teorem (1601. – 1665.).

Za svaki prosti broj p i bilo koji broj aÎ Z, nije djeljiv s p, postoji usporedba . (14)

Primjer. Neka A = 3,r= 5, gdje 3 nije 5. Tada ili .

7. 5. Fermatov generalizirani teorem.

Za bilo koji prost broj p i proizvoljan broj aÎ Dolazi do Z usporedbe (15)

TIPIČNI ZADACI

1. Dokažite da je 38 73 º 3(mod 35).

Otopina.

1) Kako je (38; 35) = 1, onda po Eulerovom teoremu ; j(35) = 24, što znači

(1).

2) Iz usporedbe (1) korolarom 2 svojstava 5 0 numeričkih usporedbi imamo:

3) Iz usporedbe (2) prema posljedici 1 svojstva 5 0 usporedbi: 38 72 ×38 º 1×38 (mod 35) Þ Þ38 73 º38 º 38–35 = 3(mod 35) Þ 38 73 º 3 (mod 35) ) , što je trebalo i dokazati.

2. S obzirom: A = 4, T= 15. Odredi najmanji eksponent k, zadovoljavajući usporedbu (*)

Otopina.

1) Budući da ( a; m) = (4; 25) = 1, tada po Eulerovom teoremu , j(25) = 20, dakle .

2) Je li pronađeni eksponent – ​​broj 20 – najmanji prirodni broj koji zadovoljava usporedbu (*)? Ako postoji eksponent manji od 20, onda on mora biti djelitelj broja 20. To znači da je traženi najmanji eksponent k morate tražiti među mnogim brojevima n= (1, 2, 4, 5, 10, 20) – djelitelji broja 20.

3) Kada n = 1: ;

na n = 2: ;

na n= 3: (ne treba razmatrati);

na n = 4: ;

na n = 5: ;

na n= 6, 7, 8, 9: (nema potrebe za razmatranjem);

na n = 10: .

Tako, najmanji eksponent k, zadovoljavajuća usporedba(*), je k= 10.

Odgovor: .

VJEŽBE ZA SAMOSTALNI RAD

141. Prema Eulerovom teoremu . Na A = 3, T= 6 imamo: .

Budući da je j(6) = 2, tada je 3 2 º1(mod 6), ili 9º1(mod 6), Tada je, prema lemi, (9 – 1) 6 ili 8 6 (potpuno!?). Gdje je greška?

142. Dokažite da je: a) 23 100 º1(mod 101); b) 81 40 º 1 (mod100); c) 2 73 º 2 (mod 73).

143. Dokažite da je a) 1 16 + 3 16 + 7 16 + 9 16 º 4 (mod 10);

b) 5 4 n + 1 + 7 4n+ 1 je djeljiv sa 12 bez ostatka.

144. Dokažite obrnuto od Eulerovog teorema: ako A j ( m) º 1(mod m), to ( a, m) =1.

145. Odredi najmanji eksponent kÎ N, zadovoljavajući ovu usporedbu: a) ; b) ; V) ; G) ;

d) ; e) ; i) ; h) .

I) ; Do) ; l) ; m) .

146. Nađi ostatak dijeljenja:

a) 7 100 do 11; b) 9 900 do 5; c) 5 176 puta 7; d) 2. 1999. do 5.; e) 8,377 do 5;

e) 26 57 puta 35; g) 35,359 puta 22; h) 5,718 do 103; i) 27 260 puta 40; j) 25. 1998. na 62.

147*. Dokažite to A 561 º A(izmjena 11).

148*. Ako kanonsko širenje prirodnog broja n ne sadrži faktore 2 i 5, tada 12. potencija tog broja završava brojem 1. Dokaži.

149*. Dokažite da je 2 64 º 16 (mod 360).

150*. Dokaži: ako ( A, 65) =1 , (b, 65) =1, dakle a 12 –b 12 je djeljiv sa 65 bez ostatka.

Poglavlje 3. ARITMETIČKE PRIMJENE

TEORIJE NUMERIČKIH USPOREĐIVANJA

§ 8. SUSTAVNI BROJEVI

OSNOVNI PODACI IZ TEORIJE

1. SUSTAVNI CIJELI BROJEVI

8. 1. Definicija 1.

Brojevni sustav je svaki način zapisivanja brojeva. Znakovi kojima su ti brojevi zapisani nazivaju se brojevima.

8. 2. Definicija 2.

Cjelobrojni nenegativan sustavni broj zapisan u t-arnom pozicijskom brojevnom sustavu naziva se broj n oblika

,gdje je i(ja = 0,1, 2,…, k) – nenegativni cijeli brojevi – znamenke, i 0 £ a ja £ t– 1, t – baza brojevnog sustava, tÎ N,t> 1.

Na primjer, zapisivanje broja u 7-arnom sustavu ima oblik: (5603) 7 = 5 × 7 3 + 6 × 7 2 + 0 × 7 1 + 3. Ovdje a ja– to su 5, 6, 0, 3 – brojevi; svi oni zadovoljavaju uvjet: 0 £ a ja£6 t=10 reci: broj n snimljeno u decimalni brojevni sustav, i indeks t= 10 ne piši.

8. 3. Teorem 1.

Bilo koji nenegativan cijeli broj može se prikazati, i to na jedinstven način, kao sustavni broj bilo koje baze t, gdje je tÎ N,t> 1.

Primjer:(1 3 9) 10 = (3 5 1) 6 = (1 0 2 4) 5 = …

8. 4. Napomena:

1) pripisivanje sustavnom broju nula s lijeve strane ne mijenja se ovaj broj:

(3 4) 5 = (0 3 4) 5 .

2) dodjela sustavnom broju s nule s desne strane su ekvivalentne množenje ovaj broj po ts: (3 4) 5 = 3×5 1 + 4; (3 4 0 0) 5 = 3×5 3 + 4×5 2 + 0×5 1 + 0 = 5 2 ×(3×5 1 + 4).

8. 5. Algoritam za pretvorbu zapisanog brojat -arni sustav, u decimalni:

Primjer: (287) 12 = 2×12 2 + 8×12 1 +7×12 0 = 2×144 + 8×12 + 7 = 288 + 96 +7 = (391) 10.

8. 6. Algoritam za pretvaranje broja zapisanog u decimali sustav, ut -ic:

Primjer: (3 9 1) 10 = (X) 12. Pronaći X.

8. 7. Operacije nad sustavnim brojevima

2. SUSTAVNI RAZLOMCI

8. 8. Definicija 3.

Konačni t-arni sustavni razlomak u brojevnom sustavu s bazom t je broj oblika

gdje c 0 Î Z, s i – brojevi– nenegativni cijeli brojevi, i 0 £ sa i£ t– 1, tÎ N,t> 1, kÎ N .

Oznaka: a = ( c 0 , S 1 S 2 …s k)t. Na t= 10 razlomak se zove decimalni.

8. 9. Korolar 1.

Svaki konačni sustavni razlomak je racionalan broj koji se može prikazati kao , gdje je aÎ Z, bÎ N.

Primjer. a = (3 1, 2 4) 6 = 3×6 + 1 + =19 + – racionalni broj. Obratna izjava je, općenito govoreći, lažna. Na primjer, razlomak se ne može pretvoriti u konačni sistematski (decimalni) razlomak.

8.10. Definicija 4.

Beskonačni t-arni pozitivni sistematski razlomak u brojevnom sustavu s bazom t je broj oblika

, gdje je c 0Î N, sa i(ja =1, 2, …, Do, …) - brojevi– nenegativni cijeli brojevi, i 0 £ sa i£ t–1, tÎ N,t> 1, kÎ N.

Oznaka: a = ( S 0 , S 1 S 2 … s k…) t. Na t=10 razlomak se zove decimalni.

8.11. Definicija 5.

Postoje tri moguće vrste beskonačnih sustavnih razlomaka:

ja = ( S 0 , )t= = t, gdje je = = = … U ovom slučaju broj a naziva se beskonačni čisto periodični razlomak,(S 1 S 2 … s k) – razdoblje, k – broj znamenki u razdoblju – duljina razdoblja.

II a = .

U ovom slučaju, broj a naziva se beskonačni mješoviti periodični razlomak, – predrazdoblje, () – razdoblje, k – broj znamenki u razdoblju – duljina razdoblja, l – broj znamenki između cijelog dijela i prve periode – duljina predperiode.

III a = ( S 0 , S 1 S 2 … s k …)t . U ovom slučaju broj a naziva se beskonačni neperiodični razlomak.

TIPIČNI ZADACI

1. Broj ( A) 5 = (2 1 4 3) 5 , dano u 5-arnom sustavu, pretvorite u 7-arni sustav, tj. pronađite X, ako je (2 1 4 3) 5 = ( X) 7 .

Otopina.

1) Pretvorite ovaj broj (2 1 4 3) 5 u broj ( na) 10, zapisano u decimalnom sustavu:

2. Slijedite ove korake:

1) (7) 8 + (5) 8 ; 2) (7) 8 × (5) 8 ; 3) (3 6 4 2) 6 + (4 3 5 1) 6 ;

4) (5 2 3 4) 7 – (2 3 5 1) 7 ; 5) (4 2 3) 5 × (3 2) 5 ; 6) (3 0 1 4 1) 5: (4 2 3) 5 .

Otopina.

1) (7) 8 + (5) 8 = (7) 10 + (5) 10 = (12) 10 = 1×8 + 4 = (1 4) 8 ;

2) (7) 8 × (5) 8 = (7) 10 × (5) 10 = (35) 10 = 4 × 8 + 3 = (4 3) 8 ;

3) (3 6 4 2) 6 + (4 3 5 1) 6 (1 2 4 3 3) 6	Bilješka:	4+5 = 9 = 1×6+3, napišite 3, 1 ide na sljedeću znamenku, 6+3+1=10 =1×6+4, napišite 4, 1 ide na sljedeću znamenku, 3+4+ 1= 8 = 1×6+2, napišite 2, 1 ide na sljedeću znamenku.
4) (5 2 3 4) 7 – (2 3 5 1) 7 (2 5 5 3) 7	Bilješka:	“zauzimamo” jedinicu najviše kategorije, tj. “1” = 1×7: (3 + 1×7) – 5 = 10 – 5 = 5, (1 + 1×7) – 3 = 8 – 3 = 5 ,
5) (4 2 3) 5 ´ (3 2) 5 (1 4 0 1) 5 + (2 3 2 4) 5__ (3 0 1 4 1) 5	Bilješka:	Kod množenja s 2: 3 × 2 = 6 = 1 × 5 + 1, upišite 1, 1 ide na sljedeću znamenku, 2 × 2 +1=5 = 1 × 5 +0, upišite 0, 1 ide na sljedeću znamenku , 2 ×4 +1=9 = 1×5 +4, napišite 4, 1 ide na sljedeću znamenku, Kada se pomnoži s 3: 3 ×3 = 9 = 1×5 + 4, napišite 4, 1 ide na sljedeću znamenka, 3 × 2 +1=7 = 1×5 +2, upišite 2, 1 ide na sljedeću znamenku, 3 ×4 +1=13=2×5 +3, upišite 3, 2 ide na sljedeću znamenku.

6) (3 0 1 4 1) 5 | (4 2 3) 5

2 3 2 4 (3 2) 5

1 4 0 1 Odgovor: 1) (1 4) 8 ; 2) (4 3) 8 ; 3) (1 2 4 3 3) 6 ; 4) (2 5 5 3) 7 ;

(0) 5 5) (3 0 1 4 1) 5 ; 6) (3 2) 5 .

VJEŽBE ZA SAMOSTALNI RAD

151. Brojevi navedeni u t-arni sustav, pretvoriti u decimalni sustav:

a) (2 3 5) 7 ; b) (2 4 3 1) 5 ; c) (1 0 0 1 0 1) 2 ; d) (1 3 ) 15 ;

e) (2 7) 11 ; f) (3 2 5 4) 6 ; g) (1 5 0 1 3) 8 ; h) (1 1 0 1 1 0 0 1) 2 ;

i) (7 6 2) 8 ; j) (1 1 1 1) 20 .

152. Brojevi. dano u decimalnom sustavu, pretvoriti u t-ički sustav. Provjerite.

a) (1 3 2) 10 = ( X) 7 ; b) (2 9 8) 10 = ( X) 5 ; c) (3 7) 10 = ( X) 2 ; d) (3 2 4 5) 10 = ( X) 6 ;

e) (4 4 4 4) 10 = ( X) 3 ; e) (5 6 3) 10 = ( X) 12 ; g) (5 0 0) 10 = ( X) 8 ; h) (6 0 0) 10 = ( X) 2 ;

i)(1 0 0 1 5) 10 =( X) 20 ; j) (9 2 5) 10 = ( X) 8 ; l) (6 3 3) 10 = ( X) 15 ; m) (1 4 3) 10 = ( X) 2 .

153. Brojevi navedeni u t-ary sustav, pretvoriti u q-arni sustav (prolaskom kroz decimalni sustav).

a) (3 7) 8 = ( X) 3 ; b) (1 1 0 1 1 0) 2 = ( X) 5 ; c) ( 6 2) 11 = ( X) 4 ;

d) (4) 12 = ( X) 9 . e) (3 3 1 3 1) 5 = ( X) 12 .

154. a) Kako će se promijeniti broj (1 2 3) 5 ako se s njegove desne strane doda nula?

b) Kako će se promijeniti broj (5 7 6) 8 ako mu se s desne strane dodaju dvije nule?

155. Slijedite ove korake:

a) (3 0 2 1) 4 + (1 2 3 3) 4 ; b) (2 6 5 4) 8 + (7 5 4 3) 8 ; c) (1 0 1 1 0 1) 2 +(1 1 0 1 10) 2 ;

d) (5 2 4 7) 9 + (1 3 7 6) 9 ; e) (4 7 6) 9 – (2 8 7) 9; e) (2 4 5 3) 7 – (1 6 4 5) 7 ;

g) (8 3) 12 – (5 7 9) 12; h) (1 7 5) 11 – (6) 11; i) (3 6 4 0 1) 7 – (2 6 6 6 3) 7 ;

j) (1 0 0 1 0) 2 × (1 1 0 1) 2 ; k) (7 4 1) 8 × (2 6) 8 ; m) (5 3 7 2) 8 × (2 4 6) 8 ;

n) (3 3 2 1) 4 × (2 3 0) 4 ; o) (1 0 2 2 2 2) 3: (1 2 2) 3 ; n) (2 1 0 3 2) 4: (3 2 3) 4 ;

p) (2 6 1 7 4) 8: (5 4 6) 8 ; c) (4 3 2 0 1) 5: (2 1 4) 5 ; t)(1 1 0 1 0 0 1 0) 2:(1 0 1 0 1) 2

y) (1 1 0 1 1 0) 2: (1 1 1) 2 ; f) (1 1 1 0) 6: (2 1 5) 6 ; x)(3 2 3 8 2 2 1 7 0) 9:(7 6 4 2) 9 .

ts) (1 6 3 5) 8 + (7 6 4) 8 ; h) (1 1 1 1) 3 – (2 1 2) 3 ; w)(1 2 7) 12 +(9 1 3 5 ) 12b" × b 1 Zatim:

I Ako je nazivnik b = b"(sadrži samo "2" i/ili "5") – tada se razlomak pretvara u konačni decimalni razlomak. Broj decimalnih mjesta jednak je najmanjem prirodnom broju l lº 0( mod b").

II Ako je nazivnik b = b 1(ne sadrži “2” i “5”), tada se razlomak pretvara u beskonačno čisto periodično jednak najmanjem prirodnom broju k, zadovoljavajuća usporedba 10 kº 1( mod b 1).

III Ako je nazivnik b = b"× b 1 (sadrži "2" i/ili "5", kao i druge proste faktore), tada se razlomak pretvara u beskonačna mješovita periodika deset-

točan razlomak.

Duljina perioda jednaka je najmanjem prirodnom broju k, zadovoljavajuća usporedba 10 kº 1( mod b 1).

Duljina predperiode jednaka je najmanjem prirodnom broju l, zadovoljavajuća usporedba 10 lº 0( mod b").

9. 2. Zaključci.

9. 3. Napomena:

racionalni broj je svaki konačni decimalni razlomak ili beskonačni periodični decimalni razlomak;

Iracionalan broj je svaki beskonačni neperiodični decimalni razlomak.

TIPIČNI ZADACI

1. Pretvorite ove obične razlomke, zapisane u decimalnom sustavu, u

decimalni prethodno određivanjem vrste traženog razlomka (konačan ili beskonačan; periodičan ili neperiodičan; ako je periodičan, onda čisto periodičan ili mješovito periodičan); u zadnjim slučajevima - unaprijed pronaći broj k– duljina i broj razdoblja l– duljina predrazdoblja. 1) ; 2) ; 3) .

Otopina.

1) Razlomak = nazivnik – broj b= 80 = 2 4 × 5 sadrži samo "2" i "5". Stoga se ovaj razlomak pretvara u konačni decimalni razlomak. Broj decimalnih mjesta l ime određuje se iz uvjeta: 10 lº0 (mod80):

2) Razlomak = nazivnik – broj b= 27 = 3 3 ne sadrži "2" i "5". Stoga se ovaj razlomak pretvara u beskonačan čisto periodično decimalni razlomak. Duljina razdoblja k ime određuje se iz uvjeta: 10 kº1(mod27):

3) Razlomak = nazivnik – broj b= 24 = 2 3 ×3, odnosno ima oblik: b = b"× b 1 (osim “2” ili “5” sadrži i druge faktore, u ovom slučaju broj 3). Stoga se ovaj razlomak pretvara u beskonačan mješoviti periodični decimalni razlomak. Duljina razdoblja k ime određuje se iz uvjeta: 10 kº1(mod3), odakle k ime= 1, odnosno duljina perioda k= 1. Duljina prije razdoblja l ime određuje se iz uvjeta: 10 lº0(mod8), odakle l ime= 3, odnosno duljina predperioda l = 3.

Provjera: “kutom” podijelimo 5 sa 24 i dobijemo: = 0,208 (3).

Odgovor: 1) 0, 0375; 2) 0, (074); 3) 0, 208 (3).

VJEŽBE ZA SAMOSTALNI RAD

156. Ove obične razlomke zapisane u decimalnom sustavu pretvorite u decimalne razlomke. Ako je decimalni razlomak periodičan, tada prethodno pronaći broj k- duljina i broj razdoblja l- duljina predrazdoblja.

157. Pretvorite ove obične razlomke zapisane u decimalnom sustavu u t-arni sustavni razlomci. Pronađite brojeve k- duljina razdoblja i l- duljina predrazdoblja.

158*. U kojem je brojevnom sustavu broj (4 6) 10 zapisan istim znamenkama, ali u

obrnutim redoslijedom?

159*. Što je veće: jedinica 8. znamenke u binarnom sustavu ili jedinica 4. znamenke u oktalnom sustavu?

§ 10. PASCALOV TEOREM. ZNAKOVI PODJELE

OSNOVNI PODACI IZ TEORIJE

10. 1. Pascalov teorem (1623 – 1662).

Zadani prirodni brojevi: t > 1i n, napisano u t - nom sustavu:

,gdje je a i – – brojevi: a iÎ N, 0 £ a ja £ t–1 (ja = 0,1, 2,…, k), tÎ N,t> 1.

Neka n= (a k a k – 1 … a 1 a 0) 10 = a k×10 k +a k – 1×10 k – 1 +…+a 1×10+ a 0 , m=3 i m = 9.

1) Pronađimo b i: modulom = 3 modulom = 9

10 0 º1(mod3), tj. b 0 =1, 10 0 º1(mod9), tj. b 0 =1,

10 1 º1(mod3), tj. b 1 =1, 10 1 º1(mod9), tj. b 1 =1,

10 2 º1(mod3), tj. b 2 =1, 10 2 º1(mod9), tj. b