Diskreetit rakenteet (ITK015)

3. DEMORATKAISUT

Ensin pelkät vastaukset lyhyesti:

1.  11, 2.  367x121 + 4x11099, 3.  7D2 ja 11111010010, 4.  a) 299 593, b) 224 694, 5.  71, 6.  a) ei, b) 2, 7.  Pätee (Fermatin viimeinen lause)

Ja sitten hieman pidemmästi:

1. Eukleideen algoritmilla syt (110099, 121)

            110099 = 91x121 + 88

            121 = 1x88 + 33

            88 = 2x33 + 22

            33 = 1x22 + 11

            22 = 2x11 + 0 => syt = 11.

2. Haetaan samalle monikertasumma.

            11 = 33 - 1x22

            11 = 33 - 1x(88 - 2x33)

            11 = 3x33 - 88

            11 = 3x(121 - 88) - 88

            11 = 3x121 - 4x88

            11 = 3x121 - 4x(11099 - 91x121)

            11 = 367x121 - 4x11099.

3. Vuosi 2002 a) heksadesimaalina ja b) binaarilukuna

a) 162 = 256 < 2002 < 4096 = 163 eli luku on "heksasatoja" ja < "heksatuhat".

                        2002/256 = 7 + 210/256 eli "heksasatoja" on 7kpl.

                        210/16 = 13 + 2/16 eli "heksakymmeniä" on 13 kpl

                        ja "heksaykkösiä" 2 kpl.                       

                        Heksadesimaalijärjestelmässä "numero" 13 on D

                        1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6

                        1 2 3 4 5 6 7 8 9 A B C D E F 0

                                                                                                            Siis 2002 = 7D2.

                        Voidaan laskea myös jakamalla luku 2002 peräkkäin 16:lla ja

                        Ottamalla "talteen" jakojäännökset eli seuraavasti:

2002/16 = 125 + 2/16, 125/16 = 7 + 13/16 ja 0 + 7 /16, jolloin

2002 = 125x16 + 2 = ((7x16) + 13)x16 + 2, josta saadaan

                        7 - 13 - 2 eli heksanumeroina 7D2.

b) 2002 = 1024 + 978 = 210 + 978

978 = 512 + 466 = 29 + 466

466 = 256 + 210 = 28 + 210

210 = 128 + 82 = 27 + 82

82 = 64 + 18 = 26 + 18

18 = 16 + 2 = 24 + 2

2 = 21 => 10 numeroinen luku 11111010010.

4. a) ABBABBABBABBABBABBA = 1001001001001001001, jossa on 19 numeroa, joista pienin 20 ja suurin 218. Näin ollen luku on kymmenjärjestelmässä:

1x218 + 0x217 + 0x216 + 1x215 + 0x214 + 0x213 + 1x212 + 0x211 + 0x210 + 1x29 + 0x28 + 0x27 + 1x26 + 0x25 + 0x24 + 1x23 + 0x22 + 0x21 + 1x20 =

218 + 215 + 212 + 29 + 26 + 23 + 20 = 299 593

            a) ABBABBABBABBABBABBA = 110110110110110110 voidaan ratkoa samoin

tai sitten laskemalla 219 - 1 - 237042 = 224 694 sillä jos sekä A että B olisivat 1

niin saadaan 1111111111111111111 = 10000000000000000000 - 1 = 219 - 1.

5. Pienimpiä alkulukuja: 2 3 5 7 11 13 17 19 23 29 31 37 41 43 47 53 59 61 67 71 73 79 83 89 97... Huomataan, että 20. alkuluku löytyy Eratostheneen seulalla jo kun alkuluku 7 on rengastettu sillä seuraava alkuluvun, 11, neliö on jo 121.

6.         a) 331 - 294 = 37 ja ei ole voimassa 2k|37 koska 2k on parillinen ja 37 lisäksi              alkuluku.

b) 65536 = 7x9362 + 2/7 => r=2. (65536 = 215)