Aritmetiska_funktioner.sagews

Aritmetiska funktioner

Låte $n$ vara ett positivt heltal. Då definieras Eulers fi-funktion $\phi(n)$ som antal positiva heltal i $\mathbb{Z}_n$ som är relativt prima med $n$.

euler_phi(12)

4

Vilka av elementen i $\mathbb{Z}_{12}$ är relativt prima med 12?

filter(lambda a : gcd(a, 12) == 1, Zmod(12).list())

[1, 5, 7, 11]

Eulers fi-funktion för heltalen $n = 2, 3, \ldots, 20$.

table([[n, euler_phi(n)] for n in [2..20]], header_row = ['n', 'fi(n)'])

n fi(n) +----+-------+ 2 1 3 2 4 2 5 4 6 2 7 6 8 4 9 6 10 4 11 10 12 4 13 12 14 6 15 8 16 8 17 16 18 6 19 18 20 8

Vi kan även illustrera funktionen grafiskt.

fi = [[n, euler_phi(n)] for n in range(1000)]
list_plot(fi, aspect_ratio = 1)

Låt $a$ vara ett heltal och $p$ ett udda primtal. Då definieras Legendresymbolen $(a/p)$ enligt $$\left(\frac{a}{p}\right) = \begin{cases} \phantom{-}1 & \text{om $x^2 \equiv a \pmod{p}$ har en lösning} \\ -1 & \text{om $x^2 \equiv a \pmod{p}$ saknar lösning} \end{cases}$$ då $\gcd(a, p) = 1$, och $(a/p) = 0$ då $p \mid a$. Notera att Lagendresymbolen är en funktion $a \mapsto (a/p)$ för olika primtal $p$. I Sage är $(a/p)$ implementerad som legendre_symbol($a$, $p$).

Är $x^2 \equiv 5 \pmod{17}$ lösbar?

legendre_symbol(5, 17)

-1

Tydligen inte. Kanske $x^2 \equiv 8 \pmod{17}$ är lösbar?

legendre_symbol(8, 17)

1

Ja! Låt oss bestämma lösningarna - det finns två stycken.

x1 = mod(8, 17).sqrt()  # en av lösningarna
x1

5

x2 = 17 - x1  # den andra lösningen
x2

12

# kontroll
x1^2, x2^2

(8, 8)

Låt $n = p_1^{a_1} p_2^{a_2} \dots p_k^{a_k}$ vara primtalsfaktoriseringen av $n$ Då definieras Möbiusfunktionen $\mu(n)$ enligt $$\mu(n) = \begin{cases} 1 & \text{om $n = 1$}\\ (-1)^k & \text{om $a_1 = a_2 = \cdots = a_k = 1$} \\ 0 & \text{annars}. \end{cases}$$ Alltså är $\mu(n) = 0$ om och endast om $a^2 \mid n$ för något heltal $a$.

table([[n, moebius(n)] for n in [1..10]], header_row = ['n', 'my(n)'])

n my(n) +----+-------+ 1 1 2 -1 3 -1 4 0 5 -1 6 1 7 -1 8 0 9 0 10 1