Matematyka dyskretna

AGH

DZIAŁ ZLICZANIE – cz. V

wszystkie zadania warte są 1 punkt

Zad. 1.
Zbadaj czy elementy a w

ma element odwrotny dla n=5,6,7,8,9.

Zad. 2.
Czy jeśli element w

może mieć dwa elementy odwrotne? Który z elementów w

nie ma

elementu odwrotnego?

Zad. 3.
Jeśli ax+ny=1, dla liczb naturalnych x i y, to czy a i n mogą mieć wspólne dzielniki różne od
1 i -1?

Zad. 4.
Jeśli a · 133−m· 277 = 1, to czy to gwarantuje, że a ma element odwrotny modulo m?

Zad. 5.

Ile jest liczb takich, że

a

·

31

22 = 1?

A ile takich, że

a

·

10

2 = 1?

Zad. 6.
Wyznacz NWD dla 210 i 126 korzystając z algorytmu Euklidesa.

Zad. 7.
Wykorzystaj rozszerzony algorytm Euklidesa do wyznaczenia odwrotności 16 modulo 103.

Zad. 8.
Pokaż, że jeśli ułamki a/b i c/d są w postaci nieskracalnej, to ich suma a/b+c/d wyrażona w
postaci nieskracalnej będzie miała mianownik równy bd wtedy i tylko wtedy gdy b i d są
względnie pierwsze.