Największy wspólny dzielnik (NWD)

Wspólny dzielnik

Przed zdefiniowaniem pojęcia największego wspólnego dzielnika, warto wyjaśnić, co oznacza wspólny dzielnik.

Wspólny dzielnik dwóch liczb naturalnych $a$ i $b$, to każda liczba naturalna $d$, która dzieli bez reszty zarówno liczbę $a$, jak i liczbę $b$.

Przykład wspólnego dzielnika

Znajdźmy wspólne dzielniki liczb $12$ i $18$.

  • Dzielniki liczby 12: $1, 2, 3, 4, 6, 12$
  • Dzielniki liczby 18: $1, 2, 3, 6, 9, 18$

Wspólne dzielniki liczb $12$ i $18$ to $1, 2, 3, 6$. Największy z nich to $6$.

Definicja największego wspólnego dzielnika

Największy wspólny dzielnik dwóch liczb naturalnych $a$ i $b$, to największa liczba naturalna, która jest wspólnym dzielnikiem obu liczb.

Przykład NWD

Znajdźmy największy wspólny dzielnik liczb $12$ i $18$.

Wspólne dzielniki tych liczb to $1, 2, 3, 6$. Największy z nich to $6$, czyli NWD(12, 18) = 6.

Metody obliczania NWD

1. Metoda rozkładu na czynniki pierwsze

  1. Rozłóż obie liczby na czynniki pierwsze.
  2. Zaznacz wspólne czynniki obu liczb.
  3. Pomnóż wspólne czynniki, aby uzyskać NWD.

Przykład dla NWD(24,36):

  • 24 = 2³ × 3
  • 36 = 2² × 3²
  • NWD(24,36) = 2² × 3 = 12

2. Algorytm Euklidesa

  1. Podziel większą liczbę przez mniejszą, zapisując resztę.
  2. Powtórz kroki, używając mniejszej liczby i reszty z poprzedniego dzielenia.
  3. Kontynuuj, aż reszta będzie równa 0. Ostatnia niezerowa reszta to NWD.

Przykład dla NWD(48,18):

  • 48 ÷ 18 = 2 (reszta 12)
  • 18 ÷ 12 = 1 (reszta 6)
  • 12 ÷ 6 = 2 (reszta 0)
  • NWD(48,18) = 6

Właściwości NWD

  1. NWD(a,b) = NWD(b,a)
  2. NWD(a,a) = a
  3. Jeżeli $a$ i $b$ są liczbami względnie pierwszymi, to NWD(a,b) = 1
  4. NWD(a,b) × NWW(a,b) = a × b

Zastosowania NWD

  • Ułamki: Przy upraszczaniu ułamków.
  • Teoria liczb: W analizie podzielności liczb.
  • Kryptografia: W algorytmach takich jak RSA.
  • Programowanie: W optymalizacji algorytmów, np. w problemach związanych z podziałem.

NWD dla więcej niż dwóch liczb

NWD można obliczać również dla więcej niż dwóch liczb, stosując metodę parami lub rozszerzając powyższe metody.

Przykład: NWD(24,36,60) = NWD(NWD(24,36),60) = NWD(12,60) = 12

Podsumowanie

Największy wspólny dzielnik jest podstawowym pojęciem w matematyce, z szerokimi zastosowaniami w teorii liczb i praktycznych problemach. Znajomość metod obliczania NWD pozwala na efektywne rozwiązywanie wielu zadań, od upraszczania ułamków po algorytmy kryptograficzne. Zrozumienie NWD jest kluczowe w matematyce i jej zastosowaniach w różnych dziedzinach.