Operacja dzielenia z resztą

Dla danych liczb całkowitych x, y, z zastrzeżeniem, że \( y \neq 0 \) określamy dwie operacje: wynik i resztę z dzielenia x przez y następująco: &nbsp;&nbsp;\( x \div y = c \), &nbsp;&nbsp;\( x\bmod y = r \), gdzie liczby c i r spełniają następujące zależności: &nbsp;&nbsp;\( x = cy + r \) oraz &nbsp;&nbsp;\( 0 \le r  <  |y| \)

Przykład

\( 11\div 3 = 3, \)
\( 11\bmod 3 = 2, \)
\( -7\div 2 = -4, \)
\( -7\bmod 2 =1, \)
\( 7\div -2 = -3, \)
\( 7\bmod -2 = 1, \)

Ćwiczenie
Czy zawsze \( x\bmod -y = -x \bmod y \) oraz \( x\div (-y) = (-x) \div y \)?

Wskazówka

Sprawdź hipotezę dla x= -7, y=3 oraz x=7, y=-3

Odpowiedź

Nie. Na przykład \( 7\div -3 = -2, -7 \div 3 = -3 \), bo \( 7 = (-2)(-3) + 1 \), a \( -7 =(-3) \cdot 3 + 2 \).

<p>PROBLEM </p> 
<p>[NWD(a,b)]: </p>
<p>Dane są dwie liczby całkowite nieujemne \( a \), \( b \) takie, że \( a + b &gt; 0 \). Wyznacz największą liczbę naturalną \( d \) taką, że \( a\bmod d \) &lt;realnowiki&gt;&lt;realnowiki&gt;= &lt;/realnowiki&gt;&lt;/realnowiki&gt;0 i \( b \bmod d= 0 \). Liczbę tę nazywamy największym wspólnym dzielnikiem \( a \) i \( b \) oraz oznaczamy przez \( (a, b) \). </p>

Zauważmy, że zawsze \( (a, b)=(b, a) \).
Załóżmy więc od tej pory, że \( a\ge b \).