rozwiaz nastepujace wyrazenia modulo mata98: rozwiaz nastepujace wyrazenia modulo 1) 7⁷²⁷mod 27 2) 13³¹mod 33

wredulus_pospolitus: jakieś pomysły

mata98: niestety brak Dlatego prosiłbym o rozwiązanie, myślę że wtedy rozjaśni mi to sprawę

wredulus_pospolitus: hmmm ... a jaką teorię już miałeś? W przypadku drugiego osobiście bym skorzystał z Chińskiego twierdzeniach o resztach 13³¹ mod 3 ≡ 1³¹ mod 3 = 1 13³¹ mod 11 ≡ 2³¹ mod 11 ≡ (2⁵)⁶*2 mod 11 ≡ 32⁶ * 2 mod 11 ≡ (−1)⁶*2 mod 11 = 2 I teraz jedziemy z w/w twierdzenia

mata98: właściwie to robimy to za pomocą funkcji Eulera, Ch.Tw. O r. nie będzie na kolokwium

mata98: ktos pomoze to rozwiazac?

Mila: 7⁷²⁷≡x(mod27) 7, 27 − liczby względnie pierwsze 1) φ(27)=18 ⇔ 7¹⁸=1(mod(27) 727=40*18+7 7⁷²⁷=(7¹⁸)⁴⁰*7⁷ 2) 7²≡(−5)( mod27) 7⁴=(7²)²=(−2) (mod27) 7⁷=7⁴*7²*7≡(−5)*(−2)*7≡16(mod27) 3) 7⁷²⁷=(7¹⁸)⁴⁰*7⁷≡1*16(mod27)≡16(mod27)

mata98: Dzięki, mam jeszcze pytanie Co w przypadku gdy liczby nie są względnie pierwsze, to jak sie ma to do wzoru: jeżeli a a jest wzglednie pierwsze z n to a^φ(n) = n¹ jak np. w przykładzie i) 15³²³mod 51 liczby 15 i 51 ? stosujemy funkcję Eulera do dwóch tych liczb?

Mila: 15³²³mod 51 15=3*5 15³²³=3³²³*5³²³mod51 1) 5³²³=x(mod51) 5⊥51 51=3*17 φ(51)=(3−1)*(17−1)=32 5³²=1( mod51) 5³²³=(5³²)¹⁰*5³ ≡1*(125 mod51)≡23(mod51) 2) CRT 3³²³=x(mod51) 3³²³=a₁(mod3)=0(mod3) 3³²³=a₂ (mod17)=10(mod17) [ 3¹⁶≡1(mod17), (3¹⁶)²⁰*3³≡27(mod17)≡17(mod17) ] a₁=0, a₂=10 m₁=3, m₂=17 M=3*17=51

	51
xi odwrotne odpowiednio do		=ni
	mi

	51		51
x=(a1*x1*		+a2*x2*		) (mod51)
	3		17

x=(0*17*x₁+10*3*x₂ )mod(51) n₂*x₂=1(mod17) ⇔3x₂=1(mod17)⇔x₂=6 x≡(0*17*x₁+10*3*6) mod(51)≡180 (mod51)≡27(mod51) 4) 3³²³*5³²³≡27*23(mod51 )≡9(mod51) ==============================