Zadanie

Narzędzia
Obiekty: Liczby pierwsze, Podzielność
Słowa kluczowe
Kategoria: Teoria liczb

ZM-20.12-KPO-9»Zadanie 9

o zadaniu...

Zadanie pochodzi z artykułu
Lemat o zwiększaniu wykładnika p-adycznego
Publikacja w Delcie: grudzień 2020
Publikacja elektroniczna: 1 grudnia 2020
Artykuł źródłowy w wersji do druku [application/pdf]: (465 KB)

Liczby $a$ i $b$ są całkowite i względnie pierwsze, a liczby $|m, n ⩾ 1$ są naturalne. Dowieść, że

n n m m NWD n,m NWD n,m NWD (a − b ,a b− ) = a b− ,

bez korzystania z algorytmu Euklidesa.

Wskazówka

Niech $|d = NWD(m, n).$ Stosując własności kongruencji, uzasadnić, że zbiór tych całkowitych $|k > 0,$ dla których $p ak− bk,$ jest postaci $|{r,2r,3r,...}.$ Stąd jeśli $p an −bn$ i $p amb−m,$ to $|p ad− bd.$ Liczby $|n/d$ i $m/d$ są względnie pierwsze, więc nie mogą obie dzielić się przez $p.$ Wywnioskować z tego, że $d d n n νp(a − b ) = νp(a − b )$ lub $|νp(ad− bd) = νp(amb−m).$ Wykorzystać własność (6) z poprzedniego kącika.