z6.pdf

PODSTAWYTEORIILICZB–ZADANIA

Zestawnr.6–RachunekKongruencji

Zad.1 Wyka»,»edla nieparzystychm,n 2 Nzachodzi

S =1 n +2 n + ... +( m − 1) n 0mod m.

Zad.2 Udowodnij,»edlawszystkich n 2 Ni p 2 Pzachodzi

n mod p 2 .

Zad.3 a)Wyka»,»edla a ? 7mamy a 3 +1lub − 1(mod7).

wsk.rozwa» a =(7 k ± i ) ,i =1 , 2 , 3.

b)oblicz2006 2007 (mod11);wsk:wzórdwumianowy

c)Jakies¡ostatniedwiecyfry9 9 9 ?

wsk.wyka»najpierw:9 10 1(mod100)oraz9 9 9(mod10).

d)Jakies¡ostatniedwiecyfry7 7 7 7

?wsk.wyka»najpierw:7 100 1(mod100)oraz7 7 7 =7 100 t · 7 43

Zad.4 Rozwi¡»kongruencj¦144 x =216(mod360).Ilemamyrozwi¡za«?

Zad.5 Wyka»,»e2 · 26! − 1(mod29)oraz18! − 1(mod437) , 437=19 · 23.

wsk.tw.Wilsona

Zad.6 Korzystaj¡czchi«skiegotwierdzeniaoresztachrozwi¡»układjednoczesnychkongruencji:

x 3(mod11) , x 5(mod19) , x 10(mod29).

wsk.standardowaproceduraiwzór. x 34433(mod6061)

Zad.7 Wyka»,»edladowolnejliczbycałkowitej n :

a) n 7 n mod42;

b) 1

a) x 2 +7 x +11 0mod5 , c) x 2 − 1mod29 ,

b) x 2 − 3 x +3 0mod7 , d) x 2 − 1mod37 .

6-1

5 n 5 + 1

3 n 3 + 7

15 n jestliczb¡całkowit¡.

Zad.8 Rozwi¡»kongruencje:

Dodatkoweproblemy–premiowanejakozadaniatrudniejsze

Zad.A Wyka»,»eje»eli p jestnieparzyst¡liczb¡pierwsz¡oraz a + b = p − 1,to

a ! b !+( − 1) a 0mod p.

Zad.B Niech p b¦dzieliczbapierwsz¡wi¦ksz¡od3iniech f ( x )=( x − 1)( x − 2) ... ( x − p +1).

Wyka»,»e p | f 0 (0).

Zad.C Dla p 2 Pfunkcj¦ f ( x )=(1 − x ) p rozwijamywszeregMaclaurina

(1 − x ) p = c 0 + c 1 x + c 2 x 2 + ...

Wyka»,»e

( 1mod p gdy p | i

0mod p gdy p - i

c i

Zad.D Wyka»,»eci¡g10 6 k +4 +3 ,k =1 , 2 ,... zawierawył¡cznieliczbyzło»one(podzielneprzez7).

Zad.E Wyka»,»eje»eli a b (mod m )tozachodzi a m b m (mod m 2 ).

wsk. a = b + t · m .Mamywi¦c a m − b m =( a − b )( ... ? ... ).Podstawzapot¦gi a wdrugimczynniku

irozwa»podzielno±¢ obu czynnikówprzez m .

Zad.F Uogólnijindukcyjniepowy»szywzórna:

dla a b (mod m )ozachodzi( a m ) n ( b m ) n (mod m n +1 ).

woparciuotenwzórokre±l,jakajestreszta R dzielenialiczby n 100 przez125.

6-2

Plik z chomika:

Inne pliki z tego folderu:

Inne foldery tego chomika: