Elementär_talteori.sagews

Elementär talteori

Heltalsfunktioner

Låt $x \in \mathbb{R}$. Funktionen $x \mapsto \lfloor x\rfloor$ kallas taket av $x$ och bestämmer det största heltal mindre än eller lika med $x$.

floor(-12.3)

-13

floor(4.7)

4

Funktionen $x \mapsto \lceil x\rceil$ kallas golvet av $x$ och bestämmer det minsta heltal större än eller lika med $x$.

ceil(-12.3)

-12

ceil(-12.3)

-12

Med round avrundar man till närmsta heltal.

round(2.3)

2

round(2.7)

3

Med signum av ett reellt tal $x$ avses funktionen $$ \mathrm{sign}(x) = \begin{cases} \phantom{-}1 & \text{om $x > 0$} \\ \phantom{-}0 & \text[om $x = 0$] \\ -1 & \text{om $xx [removed]

sign(-1234)

-1

Täljare och nämnare i ett rationellt tal fås med numerator respektive denominator.

numerator(12/5)

12

denominator(12/5)

5

Delbarhet och primtal

Låt $a$ och $b$ vara heltal, där $b > 1$. Kvoten och resten vid heltalsdivision av $a$ med $b$ bestäms med $a$ // $b$ respektive $a$ % $b$.

45 // 13

3

45 % 13

6

Alltså är $45 = 13 \cdot 3 + 6$.

Samtliga positiva delare till $154$:

divisors(154)

[1, 2, 7, 11, 14, 22, 77, 154]

Antal positiva delare till $154$:

number_of_divisors(154)

8

Med is_prime kan vi avgöra om ett heltal är ett primtal eller inte.

is_prime(154)

False

is_prime(157)

True

Funktionen nth_prime($n$) returnerar det $n$:te primtalet.

nth_prime(1)

2

nth_prime(12345)

132241

Samtliga primtal mellan $a$ och $b$ får man med prime_range($a$, $b$).

prime_range(100, 200)

[101, 103, 107, 109, 113, 127, 131, 137, 139, 149, 151, 157, 163, 167, 173, 179, 181, 191, 193, 197, 199]

Antag att du vill iterera över ala primtal mindre eller lika med $x$. En generator för iterationen fås då med primes($x$).

for p in primes(10) :
    print(p)

2 3 5 7

[p for p in primes(20)]

[2, 3, 5, 7, 11, 13, 17, 19]

Funktionen $x \mapsto \pi(x)$ bestämmer antal primtal mindre än eller lika med $x$.

prime_pi(54321)

5525

Med funktionerna previous_prime($x$) och next_prime($x$) finner vi det största primtal $p$ sådant att $p \leq x$ respektive det minsta primtal $p$ sådant att $x \leq p$.

previous_prime(14)

13

next_prime(14)

17

Primtalsfaktorisering fås med factor.

typeset_mode(True)
factor(342732)

$\displaystyle 2^{2} \cdot 3 \cdot 13^{4}$

Utdata från factor är en egen datatyp, för vilken en metod för utskrift är definierad.

typeset_mode(False)
pf = factor(342732)
type(pf)

<class 'sage.structure.factorization_integer.IntegerFactorization'>

Itererar vi över faktoriseringen ser vi att primtal och motsvarande exponent är givna som par.

[f for f in pf]

[(2, 2), (3, 1), (13, 4)]

Med andra ord kan vi komma åt enskilda primtal eller exponenter i en primtalsfaktorisering på samma sätt som då vi läser av enskilda element i en lista.

pf[1]  # andra faktorn

(3, 1)

pf[1][0]  # primtalet i den andra faktorn

3

[p for p, e in pf]  # plocka ut alla primtal i faktoriseringen

[2, 3, 13]

[p^e for p, e in pf]  # alla olika primtalspotenser

[4, 3, 28561]

Samtliga olika primtal i en faktorisering kan också bestämmas med prime_factors

prime_factors(342732)

[2, 3, 13]

Största gemensamma delare och diofantiska ekvationer

Största gemensamma delare till två heltal bestämmer man med gcd.

gcd(1234, 5678)

2

Vid fler än två heltal placerar man heltalen i en lista.

gcd([12, 18, 66, 102])

6

Funktionen xgcd($a$, $b$) returnerar $(d, x, y)$ sådana att $a x + by = d = \gcd(a, b)$.

xgcd(136, 84)

(4, -8, 13)

Alltså är $136(-8) + 84 \cdot 13 = 4$.

Minsta gemensamma multipel bestämmer man med lcm.

lcm(1234, 5678)

3503326

Låt oss lösa den diofantiska ekvationen $483x + 72y = 42$.

implicit_multiplication(True)
typeset_mode(True)
x, y = var('x y')
lsn = solve_diophantine(483x + 72y == 42)
lsn

($\displaystyle 24 \, t_{0} - 98$, $\displaystyle -161 \, t_{0} + 658$)

Vi får en parameterlösning där $t_0$ är ett godtyckligt heltal.

typeset_mode(False)
lsn[0]  # lösningen för x

24*t_0 - 98

483lsn[0] + 72lsn[1]  # sätt in lösningen i vänsterledet av ekvationen

42

Lösningen då $t_0 = 2$:

map(lambda xy : xy.subs(t_0 = 2), lsn)

[-50, 336]

Talsystem

Med funktionen digits bestämmer man siffrorna till ett heltali i valfri bas. Första siffran i listan är entalssiffran.

181172.digits(base = 2)  # den binära representationen

[0, 0, 1, 0, 1, 1, 0, 1, 1, 1, 0, 0, 0, 0, 1, 1, 0, 1]

181172.digits(base = 16, digits = '0123456789ABCDEF')  # hexadecimal representation

['4', 'B', '3', 'C', '2']

181172.digits(base = 3)  # ternär representation

[2, 0, 0, 2, 1, 1, 2, 1, 0, 0, 0, 1]

Heltalet 181172 har således den binära representationen 101100001110110100 och den hexadecimala representationen 2C3B4 samt i basen $3$ har heltalet formen 100012112002.

Att konverterar från valfri bas till decimalbas, d.v.s. 10, görs via ZZ.

ZZ('1101101', base = 2)

109

ZZ([2, 0, 1, 1], base = 3)

38

ZZ([1, 2, 3], base = 10)  # tänk på ordningen i en lista

321

ZZ('123', base = 10)  # i en textsträng står siffrorna i den ordning vi är vana vid

123

ZZ('A3019B', base = 16)

10682779

Konguensteori

Mängden $\mathbb{Z}_n = \{0, 1, \ldots n - 1\}$ definieras med Zmod.

typeset_mode(True)
Z28 = Zmod(28)
Z28

$\displaystyle \ZZ/28\ZZ$

print Z28

Ring of integers modulo 28

Samtliga element i $\mathbb{Z}_{28}$.

Z28.list()

[$\displaystyle 0$, $\displaystyle 1$, $\displaystyle 2$, $\displaystyle 3$, $\displaystyle 4$, $\displaystyle 5$, $\displaystyle 6$, $\displaystyle 7$, $\displaystyle 8$, $\displaystyle 9$, $\displaystyle 10$, $\displaystyle 11$, $\displaystyle 12$, $\displaystyle 13$, $\displaystyle 14$, $\displaystyle 15$, $\displaystyle 16$, $\displaystyle 17$, $\displaystyle 18$, $\displaystyle 19$, $\displaystyle 20$, $\displaystyle 21$, $\displaystyle 22$, $\displaystyle 23$, $\displaystyle 24$, $\displaystyle 25$, $\displaystyle 26$, $\displaystyle 27$]

Låt oss tilldela två variabler element ur $\mathbb{Z}_{28}$.

a = Z28(11)
b = Mod(6, 28)

Det ser ut att vara helt vanligt heltal. Men Sage uppfattar dem som element i $\mathbb{Z}_{28}$.

b

$\displaystyle 6$

parent(b)

$\displaystyle \ZZ/28\ZZ$

b in Z28

$\displaystyle \mathrm{True}$

Vid beräkningar bestäms resten modulo $28$ automatiskt.

a + 4 b

$\displaystyle 7$

Lyfter vi elementen till heltal före beräkningarna får vi ett helt annat resultat.

a.lift() + 4 b.lift()

$\displaystyle 35$

Notera att $35 \equiv 7 \pmod{28}$.

I de fall då ett element $x$ är inverterbar kan vi skriva x^(-1) för att bestämma dess multiplikativa invers.

a^(-1)

$\displaystyle 23$

Alltså är $23 \cdot 11 \equiv 1 \pmod{28}$.

23 a  # kontroll

$\displaystyle 1$

För att beräkna $a^n$ modulo $m$ kan man använda funktionen power_mod($a$, $n$, $m$). Låt oss beräkna $1234^{5678}$ modulo $111111$.

power_mod(1234, 5678, 111111)

$\displaystyle 22894$

Notera att $1234^{5678}$ är ett stort heltal.

len((1234^5678).digits())  # antal siffror

$\displaystyle 17553$

Låt oss lösa konguensen $12x \equiv 3 \pmod{15}$.

x = var('x')
solve_mod(12x == 3, 15)

[($\displaystyle 9$), ($\displaystyle 4$), ($\displaystyle 14$)]

Antag att vi vill lösa kongruenssystemet ParseError: KaTeX parse error: Unknown column alignment: @ at position 36: … \begin{array}{@̲{}l@{}} … Eftersom $\gcd(451, 665) = 1$ har systemet en entydigt lösning modulo $561 \cdot 665$ enligt kinesiska restsatsen. I Sage löser man systemet med funktionen crt (Chinese Remainder Theorem).

crt([71, 11], [561, 665])

$\displaystyle 359111$