Ojlerova funkcija-pomoc

Ojlerova funkcija-pomoc 22.05.2005. u 11:59 · pre 261 mesec #1

Potrebno objasnjenje ova dva zadatka
1)
2^(n-1) kongruentno sa 1 (mod n) , gde je n=37*73

2)
p i q su dva razlicita prosta broja
p^(q-1)+q^(p-1) kongruentno sa 1 (mod pq)

Znam da ima veze sa Ojlerovom funkcijom...

Re: Ojlerova funkcija-pomoc 22.05.2005. u 17:59 · pre 261 mesec #2

Broj $p^{q-1}+q^{p-1}-1$ je deljiv sa $p$ , jer je $p^{q-1}$ deljivo sa $p$ , kao i $q^{p-1}-1$ (na osnovu male Fermaove teoreme, koja je specijalni slucaj Ojlerove teoreme). Slicno je broj $p^{q-1}+q^{p-1}-1$ deljiv i sa $q$ , pa je deljiv i sa $pq$ . Zbog toga je $p^{q-1}+q^{p-1}\equiv 1\ (mod\ pq)$ . Za ovaj drugi nemam vremena sad da kucam, pa ce postaviti resenje sutra ili prekosutra (ako me neko ne preduhitri).

Re: Ojlerova funkcija-pomoc 23.05.2005. u 00:51 · pre 261 mesec #3

Za Ojlerovu funkciju važi:
$\varphi (n)$ je broj brojeva k, takvih da $1\le k<n\quad\wedge\quad NZD(k,n)=1$
$NZD(a,b)=1\quad\Rightarrow\quad\varphi(ab)=\varphi(a)\varphi(b)$
p-prost $\quad\Rightarrow\quad\varphi(p^n)=p^n-p^{n-1}$

Npr
$\varphi (37)=37-1=36 \\ \varphi (73)=73-1=72$
$\varphi(37\cdot 73)=\varphi(37)\varphi(73)=36\cdot 72$

Ojlerova teorema
NZD(a,b)=1 $\quad\Rightarrow\quad b^{\varphi(a)} \equiv 1(mod\ a)$

Posledica Ojlerove teoreme
Neka je $k\equiv r(mod\ \varphi(a))$ i NZD(a,b)=1
Tada je $b^k\equiv b^r(mod\ a)$

Prvo ćemo videti čemu je kongruentno $x=2^{n-1}$ po modulu 37, pa po modulu 73. No, pre toga moramo da vidimo čemu je kongruentno samo n-1 po modulu $\varphi (37)$ =36 te po modulu $\varphi (73)$ =72

$37\cdot 73 -1\equiv 37\cdot 1-1 \equiv 36(mod\ 72)$
$37\cdot 73-1\equiv 1\cdot 1 -1\equiv 0(mod\ 36)$

Ovde smo mogli da koristimo stav
$a\equiv b(mod\ nc)\quad \Rightarrow \quad a\equiv b(mod\ c)$
pa bi smo dobili
$n-1\equiv 36 \equiv 0(mod\ 36)$

Obeležimo sa $x=2^{n-1}$

Daklem
$x\equiv 2^0\equiv 1(mod\ 37)$
$x\equiv 2^{36}(mod\ 37)$

Za ovo drugo računajmo
$2^3\equiv 8 (mod\ 73) \\ 2^6\equiv 8^2\equiv -9(mod\ 73) \\ 2^9\equiv 2^6\cdot 2^3\equiv 8\cdot (-9)\equiv -72\equiv 1 (mod\ 73)$

Dakle
$x\equiv (2^9)^4\equiv 1 (mod\ 73)$

Eh, sad kineska teorema o ostacima

Kineska teorema o ostacima
Ako je $x\equiv \alpha (mod\ a)$ i $x\equiv \beta (mod\ b)$ i NZD(a,b)=1, tada jednačina
$x \equiv y(mod\ ab)\quad ,\quad (0\le y< b)$
ima jedinstveno rešenje po y.

Uz dodatak

Posledica Kineske teoreme o ostacima
Ako je $x\equiv \alpha (mod\ a)$ i $x\equiv \beta (mod\ b)$ i ap+bq=1, tada je
$x\equiv a\cdot p\cdot \beta +b\cdot q\cdot \alpha(mod\ ab)$

Daklem, pošto je $38\cdot 32-15\cdot 81=1$ , vidimo da je
$x\equiv 38\cdot 32-15\cdot 81\equiv 1 (mod\ 37\cdot73)$

Ovaj drugi deo mogao je i bez posledice kineske teoreme, jer

$x\equiv 1(mod\ 37\cdot 73)\quad \Rightarrow ((x\equiv 1 (mod\ 37)) \ \wedge (x\equiv 1 (mod\ 73))$

pa bi smo do rešenja stigli praktično pogađanjem. Obrati pažnju da bez kineske teoreme ne smemo da tvrdimo da je $x\equiv 1(mod\ 37\cdot 73)$ , zbog jedinstvenosti koju nam daje baš kineska teorema.

Najzad da napomenem
$a=b\quad\Rightarrow a\equiv b(mod c)\ (\forall c)$
te stoga nema potrebe da koristiš jednakosti.

Za kraj, još jedna teorema
$a\equiv b(mod\ c)\quad\Rightarrow\quad a\cdot n\equiv b\cdot n(mod\ c\cdot n)$

Forum kao aplikacija na telefonu

Srodne teme