Tehtävässä tulee laskea Eulerin φ-funktio $\phi(n)$, joka määrittelee niiden lukujen määrän väliltä 1 ja $n$, jotka ovat suhteellisia alkulukuja $n$:n kanssa. Laskut suoritetaan jokaiselle annetulle $n$-arvolle.

a) $n = 37$
Koska 37 on alkuluku, niin Eulerin φ-funktiolle pätee: $\phi(37) = 37 - 1 = 36$ Alkuluvun kohdalla φ-funktion arvo on aina $n-1$, koska kaikki luvut 1 ja $n$-välistä ovat suhteellisia alkulukuja.

b) $n = 252$
Lasketaan ensin luvun 252 alkutekijähajotelma: $252 = 2^2 \cdot 3^2 \cdot 7$ Tällöin Eulerin φ-funktion arvo voidaan laskea seuraavalla kaavalla: $\phi(n) = n \left(1 - \frac{1}{p_1}\right) \left(1 - \frac{1}{p_2}\right) \cdots \left(1 - \frac{1}{p_k}\right)$ missä $p_1, p_2, \dots, p_k$ ovat luvun alkutekijät. Sijoitetaan $n = 252$: $\phi(252) = 252 \left(1 - \frac{1}{2}\right) \left(1 - \frac{1}{3}\right) \left(1 - \frac{1}{7}\right) = 252 \times \frac{1}{2} \times \frac{2}{3} \times \frac{6}{7}$ Lasketaan tämä: $\phi(252) = 126 \times \frac{2}{3} = 84 \times \frac{6}{7} = 72$

c) $n = 1776$
Lasketaan ensin luvun 1776 alkutekijähajotelma: $1776 = 2^4 \cdot 3 \cdot 37$ Sijoitetaan Eulerin φ-kaavaan: $\phi(1776) = 1776 \left(1 - \frac{1}{2}\right) \left(1 - \frac{1}{3}\right) \left(1 - \frac{1}{37}\right)$ Lasketaan: $\phi(1776) = 1776 \times \frac{1}{2} \times \frac{2}{3} \times \frac{36}{37}$ $\phi(1776) = 888 \times \frac{2}{3} = 592 \times \frac{36}{37} \approx 576$

Vastaukset: a) $\phi(37) = 36$
b) $\phi(252) = 72$
c) $\phi(1776) \approx 576$

Haluatko tarkempia yksityiskohtia laskuista tai lisäkysymyksiä?

Tässä on 5 aiheeseen liittyvää kysymystä:

1. Mikä on Eulerin φ-funktion merkitys lukuteoriassa?
2. Kuinka Eulerin φ-funktio käyttäytyy alkuluvuilla verrattuna yhdistelmälukuihin?
3. Miten Eulerin φ-funktio liittyy RSA-salausalgoritmiin?
4. Voiko Eulerin φ-funktion arvo olla suurempi kuin $n-1$? Perustele.
5. Mikä on suurin mahdollinen φ-arvo tietyllä välillä $1$ ja $n$?

Vinkki: Jos luku $n$ on alkuluku, φ-funktion laskeminen on hyvin yksinkertaista, koska silloin $\phi(n) = n - 1$.