Układ kongurencji do chińskiego Twiedzenia o resztach
: 10 sty 2016, o 19:06
Witam, próbuje rozwiązać zadanie korzystając z chińskiego twierdzenia o resztach, jednak sprawia mi problem zrozumienie jak rozwiązywać pojedyńcze kongurencje:
\(\displaystyle{ 28 y \equiv 1 \ ( mod \ 5)}\)
\(\displaystyle{ 35 y \equiv 1 \ ( mod \ 4)}\)
\(\displaystyle{ 20 y \equiv 1 \ ( mod \ 7)}\)
znam rozwiązania ale nie wiem jak do nich dojsc, rozwiązując rozszerzonym algorytmem euklidesa w taki sposob jak np:
\(\displaystyle{ 99x\equiv 1(mod13)}\) wychodzi \(\displaystyle{ 1=5\cdot99-38\cdot13}\) wiec rozwiązaniem jest \(\displaystyle{ x=5}\) i to sie zgadza bo \(\displaystyle{ 495 = 1 mod 13}\)
ale w moim przypadku:
\(\displaystyle{ 20 y \equiv 1 \ ( mod \ 7)}\) wychodzi mi cos takiego jak \(\displaystyle{ 1= 3 \cdot 7 - 20}\) i wychodzi mi \(\displaystyle{ -1}\) a to sie niestety nie zgadza, biorę nie tą wartosć co trzeba? wiem ze wynikiem jest \(\displaystyle{ 6}\) ale nie wiem skad.
\(\displaystyle{ 28 y \equiv 1 \ ( mod \ 5)}\)
\(\displaystyle{ 35 y \equiv 1 \ ( mod \ 4)}\)
\(\displaystyle{ 20 y \equiv 1 \ ( mod \ 7)}\)
znam rozwiązania ale nie wiem jak do nich dojsc, rozwiązując rozszerzonym algorytmem euklidesa w taki sposob jak np:
\(\displaystyle{ 99x\equiv 1(mod13)}\) wychodzi \(\displaystyle{ 1=5\cdot99-38\cdot13}\) wiec rozwiązaniem jest \(\displaystyle{ x=5}\) i to sie zgadza bo \(\displaystyle{ 495 = 1 mod 13}\)
ale w moim przypadku:
\(\displaystyle{ 20 y \equiv 1 \ ( mod \ 7)}\) wychodzi mi cos takiego jak \(\displaystyle{ 1= 3 \cdot 7 - 20}\) i wychodzi mi \(\displaystyle{ -1}\) a to sie niestety nie zgadza, biorę nie tą wartosć co trzeba? wiem ze wynikiem jest \(\displaystyle{ 6}\) ale nie wiem skad.