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.