Układ równań modulo - iloraz dwóch liczb

[huteusz]

Liczba \(\displaystyle{ x}\) dodatnia trzycyfrowa, dająca resztę \(\displaystyle{ 7}\) przy dzieleniu przez \(\displaystyle{ 9}\) i \(\displaystyle{ 10}\) oraz resztę \(\displaystyle{ 3}\) przy dzieleniu przez \(\displaystyle{ 11}\) jest dzielnikiem liczby \(\displaystyle{ y}\) dodatniej sześciocyfrowej, która daje resztę \(\displaystyle{ 8}\) przy dzieleniu przez \(\displaystyle{ 8}\), resztę \(\displaystyle{ 7}\) przy dzieleniu przez \(\displaystyle{ 10}\), oraz resztę \(\displaystyle{ 1}\) przy dzieleniu przez \(\displaystyle{ 11}\). Znajdź iloraz \(\displaystyle{ \frac{y}{x}}\)

Jak się zabrać za takie zadanie? Łatwo jest ułożyć układ kongurencji i wyliczyć \(\displaystyle{ x}\) oraz \(\displaystyle{ y}\), tylko czy do czegoś się to przyda, jak to wykorzystać? Zwłaszcza, że obie liczby wyjdą \(\displaystyle{ \pmod{ 990}}\).

Mam w notatkach wskazówkę, że trzeba zrobić układ ze zmienną \(\displaystyle{ \frac{y}{x}}\), jednak nie mam kompletnie pomysłu jak to zrobić. Przecież, gdy weźmiemy np, \(\displaystyle{ x = 2 \pmod{ 4}}\) oraz \(\displaystyle{ y = 3 \pmod{ 4}}\), to \(\displaystyle{ \frac{x}{y} \pmod{ 4}}\) może mieć wiele różnych rozwiązań...
Istotnym faktem chyba jest jednak to, że \(\displaystyle{ x}\) jest dzielnikiem \(\displaystyle{ y}\).

Chyba, że ten układ ma na tyle mało rozwiązań że to się da sprawdzić "ręcznie".. zaraz jeszcze spróbuję przeliczyć.

Wyliczyłem że:
\(\displaystyle{ \begin{cases} x=267 \pmod{ 990} \\ y=287 \pmod{ 990} \end{cases}}\)


Pozdrawiam i dzięki za wskazówki!

[vpprof]

Liczba x dodatnia trzycyfrowa, dająca resztę 7 przy dzieleniu przez 9 i 10 oraz resztę 3 przy dzieleniu przez 11

To już jednoznacznie identyfikuje tę liczbę.

\(\displaystyle{ 90|x-7}\), zatem \(\displaystyle{ x=7+90k}\), przy czym \(\displaystyle{ 100 \le x \le 999}\), a więc \(\displaystyle{ 2 \le k \le 11}\). Interesują nas liczby od \(\displaystyle{ 187}\) do \(\displaystyle{ 997}\).

Któraś z tych liczb daje resztę \(\displaystyle{ 3}\) przy dzieleniu przez \(\displaystyle{ 11}\) (liczb jest dziesięć, no ale powiedzmy, że nie idziemy na łatwiznę). Czyli \(\displaystyle{ 7+90k=3+11k' \Leftrightarrow 4+2k=0 \pmod{11} \Leftrightarrow k=-2=9 \pmod{11}}\). W podanym zakresie jest tylko jedna taka liczba, jest to właśnie dziewięć, a \(\displaystyle{ x=817}\).

Myślę, że z tą drugą liczbą można byłoby przeprowadzić podobne rozumowanie.

[kropka+]

Co do igraka to wiadomo tylko, że kończy się na 7, natomiast to co napisałeś

która daje resztę 8 przy dzieleniu przez 8

mija się z prawdą.

[vpprof]

Co do igraka to wiadomo tylko, że kończy się na 7, natomiast to co napisałeś

która daje resztę 8 przy dzieleniu przez 8

mija się z prawdą.

Może chodziło o resztę przy dzieleniu przez \(\displaystyle{ 9}\), jak w przypadku \(\displaystyle{ x}\), tym bardziej że gdzieś wyszło mu modulo \(\displaystyle{ 990=9 \cdot 10 \cdot 11}\)…-- 6 sty 2014, o 20:36 --

Co do igraka to wiadomo tylko, że kończy się na 7

Nie. \(\displaystyle{ y}\) można wyliczyć tak samo jak \(\displaystyle{ x}\).

\(\displaystyle{ y=8+9k=7+10k'=1+11k'' \\
8+9k=7 \pmod{10} \\
k=1 \pmod{10} \\
k=1+10c \\
8+9(1+10c)=1+11k'' \\
17+90c=1 \pmod{11} \\
5+2c=0 \pmod{11} \\
c=3 \pmod{11} \\
c=3+11c'}\)

Zatem po uwzględnieniu trzech kongruencji:

\(\displaystyle{ y=8+9(1+10(3+11c'))=287+990c'}\) (to co wyliczył huteusz)

Dodając warunek, że \(\displaystyle{ x|y}\) mamy:

\(\displaystyle{ y=287+990c'=0 \pmod{x} \\
c'=530 \cdot 173^{-1} \pmod{817}}\)

Pozostaje nam wyliczyć odwrotność \(\displaystyle{ 173}\) w \(\displaystyle{ \ZZ_{817}}\) np. algorytmem Euklidesa — wychodzi \(\displaystyle{ -85 \equiv_{817} 732}\), zatem \(\displaystyle{ c'=732 \cdot 530=702 \pmod{817}}\). Ostatecznie \(\displaystyle{ y=287+990(702+817c'')=695267+808830c''}\). Ponieważ \(\displaystyle{ 100000 \le y \le 999999}\), to \(\displaystyle{ c''=0,\ y=695267}\).

Szukany iloraz to \(\displaystyle{ 851}\). Pewnie można było sprytniej, ale po co, skoro liczenia nie jest dużo a wszystko jest podane w zadaniu…

[huteusz]

Tak, chodziło o resztę przy dzieleniu przez 9, musiałem się pomylić.
Również dostałem natchnienie i zastosowałem pomysł vpprof, jeszcze nim się tu pojawił
Tylko że powychodziły mi nieco inne liczby, ale może to moja pomyłka, co więcej wyszło mi więcej takich sześciocyfrowych liczb.
Przejrzę to jeszcze, a myśle że potomni wyciągną odpowiednio dużo wniosków z tego zadania już po tym co tu jest zapisane.

Dziękuję za pomoc!