Powered by CoCalc

Elementär talteori

Heltalsfunktioner

Låt xRx \in \mathbb{R}. Funktionen xxx \mapsto \lfloor x\rfloor kallas taket av xx och bestämmer det största heltal mindre än eller lika med xx.
floor(-12.3)
-13
floor(4.7)
4
Funktionen xxx \mapsto \lceil x\rceil kallas golvet av xx och bestämmer det minsta heltal större än eller lika med xx.
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 xx avses funktionen
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 aa och bb vara heltal, där b>1b > 1. Kvoten och resten vid heltalsdivision av aa med bb bestäms med aa // bb respektive aa % bb.
45 // 13
3
45 % 13
6
Alltså är 45=133+645 = 13 \cdot 3 + 6.
Samtliga positiva delare till 154154:
divisors(154)
[1, 2, 7, 11, 14, 22, 77, 154]
Antal positiva delare till 154154:
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(nn) returnerar det nn:te primtalet.
nth_prime(1)
2
nth_prime(12345)
132241
Samtliga primtal mellan aa och bb får man med prime_range(aa, bb).
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 xx. En generator för iterationen fås då med primes(xx).
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π(x)x \mapsto \pi(x) bestämmer antal primtal mindre än eller lika med xx.
prime_pi(54321)
5525
Med funktionerna previous_prime(xx) och next_prime(xx) finner vi det största primtal pp sådant att pxp \leq x respektive det minsta primtal pp sådant att xpx \leq p.
previous_prime(14)
13
next_prime(14)
17
Primtalsfaktorisering fås med factor.
typeset_mode(True) factor(342732)
223134\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(aa, bb) returnerar (d,x,y)(d, x, y) sådana att ax+by=d=gcd(a,b)a x + by = d = \gcd(a, b).
xgcd(136, 84)
(4, -8, 13)
Alltså är 136(8)+8413=4136(-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=42483x + 72y = 42.
implicit_multiplication(True) typeset_mode(True) x, y = var('x y') lsn = solve_diophantine(483x + 72y == 42) lsn
(24t098\displaystyle 24 \, t_{0} - 98, 161t0+658\displaystyle -161 \, t_{0} + 658)
Vi får en parameterlösning där t0t_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å t0=2t_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 33 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 Zn={0,1,n1}\mathbb{Z}_n = \{0, 1, \ldots n - 1\} definieras med Zmod.
typeset_mode(True) Z28 = Zmod(28) Z28
Z/28Z\displaystyle \ZZ/28\ZZ
print Z28
Ring of integers modulo 28
Samtliga element i Z28\mathbb{Z}_{28}.
Z28.list()
[0\displaystyle 0, 1\displaystyle 1, 2\displaystyle 2, 3\displaystyle 3, 4\displaystyle 4, 5\displaystyle 5, 6\displaystyle 6, 7\displaystyle 7, 8\displaystyle 8, 9\displaystyle 9, 10\displaystyle 10, 11\displaystyle 11, 12\displaystyle 12, 13\displaystyle 13, 14\displaystyle 14, 15\displaystyle 15, 16\displaystyle 16, 17\displaystyle 17, 18\displaystyle 18, 19\displaystyle 19, 20\displaystyle 20, 21\displaystyle 21, 22\displaystyle 22, 23\displaystyle 23, 24\displaystyle 24, 25\displaystyle 25, 26\displaystyle 26, 27\displaystyle 27]
Låt oss tilldela två variabler element ur Z28\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 Z28\mathbb{Z}_{28}.
b
6\displaystyle 6
parent(b)
Z/28Z\displaystyle \ZZ/28\ZZ
b in Z28
True\displaystyle \mathrm{True}
Vid beräkningar bestäms resten modulo 2828 automatiskt.
a + 4 b
7\displaystyle 7
Lyfter vi elementen till heltal före beräkningarna får vi ett helt annat resultat.
a.lift() + 4 b.lift()
35\displaystyle 35
Notera att 357(mod28)35 \equiv 7 \pmod{28}.
I de fall då ett element xx är inverterbar kan vi skriva x^(-1) för att bestämma dess multiplikativa invers.
a^(-1)
23\displaystyle 23
Alltså är 23111(mod28)23 \cdot 11 \equiv 1 \pmod{28}.
23 a # kontroll
1\displaystyle 1
För att beräkna ana^n modulo mm kan man använda funktionen power_mod(aa, nn, mm). Låt oss beräkna 123456781234^{5678} modulo 111111111111.
power_mod(1234, 5678, 111111)
22894\displaystyle 22894
Notera att 123456781234^{5678} är ett stort heltal.
len((1234^5678).digits()) # antal siffror
17553\displaystyle 17553
Låt oss lösa konguensen 12x3(mod15)12x \equiv 3 \pmod{15}.
x = var('x') solve_mod(12x == 3, 15)
[(9\displaystyle 9), (4\displaystyle 4), (14\displaystyle 14)]
Antag att vi vill lösa kongruenssystemet Eftersom gcd(451,665)=1\gcd(451, 665) = 1 har systemet en entydigt lösning modulo 561665561 \cdot 665 enligt kinesiska restsatsen. I Sage löser man systemet med funktionen crt (Chinese Remainder Theorem).
crt([71, 11], [561, 665])
359111\displaystyle 359111