\(\displaystyle{ \begin{cases} x \equiv a\ mod\ m \\ x \equiv b\ mod \ n \end{cases}}\)
Udowodnij, że układ ma rozwiązanie całkowite wtw gdy gcd(m,n) jest dzielnikiem (a-b).
Mam problem z implikacją w prawo.
Dowód- nwd i podzielność
-
xiikzodz
- Użytkownik
- Posty: 1874
- Rejestracja: 4 paź 2008, o 02:13
- Płeć: Kobieta
- Lokalizacja: Lost Hope
- Podziękował: 28 razy
- Pomógł: 502 razy
Dowód- nwd i podzielność
Niech \(\displaystyle{ x}\) będzie rozwiązaniem tego układu. Wówczas
\(\displaystyle{ x=sm+a=tn+b}\)
Skąd
\(\displaystyle{ tn-sm=a-b}\).
Zauważmy, że
\(\displaystyle{ \gcd(m,n)}\)
dzieli lewa stronę, wiec dzieli rownież prawa.
(Implikacja w lewo, gdyby to jednak o nia chodziło, wynika z algorytmu Euklidesa:
Istnieją \(\displaystyle{ s,t}\) takie, ze
\(\displaystyle{ \gcd(m,n)=sm-tn}\).
Wówczas
\(\displaystyle{ x=\frac{b-a}{\gcd(m,n)}\cdot sm+ a}\)
jest rozwiązaniem układu równan.)
\(\displaystyle{ x=sm+a=tn+b}\)
Skąd
\(\displaystyle{ tn-sm=a-b}\).
Zauważmy, że
\(\displaystyle{ \gcd(m,n)}\)
dzieli lewa stronę, wiec dzieli rownież prawa.
(Implikacja w lewo, gdyby to jednak o nia chodziło, wynika z algorytmu Euklidesa:
Istnieją \(\displaystyle{ s,t}\) takie, ze
\(\displaystyle{ \gcd(m,n)=sm-tn}\).
Wówczas
\(\displaystyle{ x=\frac{b-a}{\gcd(m,n)}\cdot sm+ a}\)
jest rozwiązaniem układu równan.)