Matematyka.pl

W zbiorze liczb całkowitych.
Reszta z dzielenia liczby \(\displaystyle{ l}\) przez liczbę \(\displaystyle{ p}\) wynosi \(\displaystyle{ r_{1} }\), a przez liczbę \(\displaystyle{ q}\) wynosi \(\displaystyle{ r_{2} }\).
Wyznaczyć resztę z dzielenia liczby \(\displaystyle{ l}\) przez \(\displaystyle{ pg}\).
Próbowałem następująco:
\(\displaystyle{ l=pn+r_{1}\\l=qm+r_{2}}\)

\(\displaystyle{ ql=qpn+qr_{1} \\pl=pqm+pr_{2}}\)
Jeżeli \(\displaystyle{ \left| p-g\right|=1}\), to wystarczy odpowiednio odjąć stronami i koniec zadania.
Na przykład dla \(\displaystyle{ q>p}\) mamy
\(\displaystyle{ ql-pl=qpn+qr_{1}-pqm-pr_{2}\\
(q-p)l=qp(n-m)+pr_{1}-qr_{2}}\)
Wtedy reszta z dzielenia liczby l przez \(\displaystyle{ pq}\) wynosi \(\displaystyle{ pr_{1}-qr_{2}}\),
Oczywiście jeśli \(\displaystyle{ pr_{1}-qr_{2}<0}\) należało by zapisać
\(\displaystyle{ l=qp(n-m-e)+pr_{1}-qr_{2}+qpe}\), gdzie \(\displaystyle{ e=\lceil \frac{qr_{2}-pr_{1}}{pq}\rceil }\)
Więc przyjmę, że \(\displaystyle{ \left| p-g\right| \neq 1}\).
Trzeba dobrać takie liczby \(\displaystyle{ a,b}\), że
\(\displaystyle{ qa-bp=1}\)
Gdy liczby nie są względnie pierwsze, np \(\displaystyle{ p=zq}\), wtedy \(\displaystyle{ a= \frac{bp+1}{q}=\frac{bzq+1}{q}=\frac{bzq}{q}+\frac{1}{q}=bz+\frac{1}{q}}\)
W takim wypadku, czy ta metoda działa, wtedy i tylko wtedy gdy \(\displaystyle{ NWD(p,q)=1}\)?

MateuszWojnarowski pisze: ↑14 wrz 2022, o 21:57 Reszta z dzielenia liczby \(\displaystyle{ l}\) przez liczbę \(\displaystyle{ p}\) wynosi \(\displaystyle{ r_{1} }\), a przez liczbę \(\displaystyle{ q}\) wynosi \(\displaystyle{ r_{2} }\).Wyznaczyć resztę z dzielenia liczby \(\displaystyle{ l}\) przez \(\displaystyle{ pg}\).

Według mnie zadanie jest źle sformułowane. Jeśli odpowiedź ma nie zależeć od \(\displaystyle{ l}\), to istnieją przykłady, które dają takie samo \(\displaystyle{ r_1}\) i \(\displaystyle{ r_2}\) jednak inny wynik końcowy. Dla przykładu \(\displaystyle{ p=q=2}\) oraz \(\displaystyle{ l=2}\) lub \(\displaystyle{ l=4}\)

Próbowałem następująco:
\(\displaystyle{ l=pn+r_{1}\\l=qm+r_{2}}\)

\(\displaystyle{ ql=qpn+qr_{1} \\pl=pqm+pr_{2}}\)
Jeżeli \(\displaystyle{ \left| p-g\right|=1}\), to wystarczy odpowiednio odjąć stronami i koniec zadania.
Na przykład dla \(\displaystyle{ q>p}\) mamy
\(\displaystyle{ ql-pl=qpn+qr_{1}-pqm-pr_{2}\\
(q-p)l=qp(n-m)+pr_{1}-qr_{2}}\)
Wtedy reszta z dzielenia liczby l przez \(\displaystyle{ pq}\) wynosi \(\displaystyle{ pr_{1}-qr_{2}}\),

Szczerze mówiąc nie przekonało mnie to rozumowanie, bo niby dlaczego \(\displaystyle{ pr_{1}-qr_{2}< pq}\) ?

Oczywiście jeśli \(\displaystyle{ pr_{1}-qr_{2}<0}\) należało by zapisać
\(\displaystyle{ l=qp(n-m-e)+pr_{1}-qr_{2}+qpe}\), gdzie \(\displaystyle{ e=\lceil \frac{qr_{2}-pr_{1}}{pq}\rceil }\)

Tu przydałoby się uzasadnienie, że \(\displaystyle{ 0 \leq pr_{1}-qr_{2}+qpe < pq}\).

Więc przyjmę, że \(\displaystyle{ \left| p-g\right| \neq 1}\).
Trzeba dobrać takie liczby \(\displaystyle{ a,b}\), że
\(\displaystyle{ qa-bp=1}\)

Czemu ?

Gdy liczby nie są względnie pierwsze, np \(\displaystyle{ p=zq}\),

To nie jest zaprzeczenie względnej pierwszości.

wtedy \(\displaystyle{ a= \frac{bp+1}{q}=\frac{bzq+1}{q}=\frac{bzq}{q}+\frac{1}{q}=bz+\frac{1}{q}}\)

Czym są \(\displaystyle{ a}\) i \(\displaystyle{ b}\) ?

W takim wypadku, czy ta metoda działa, wtedy i tylko wtedy gdy \(\displaystyle{ NWD(p,q)=1}\)?

Jaka metoda?

matmatmm pisze: ↑14 wrz 2022, o 23:14 Według mnie zadanie jest źle sformułowane. Jeśli odpowiedź ma nie zależeć od \(\displaystyle{ l}\), to istnieją przykłady, które dają takie samo \(\displaystyle{ r_1}\) i \(\displaystyle{ r_2}\) jednak inny wynik końcowy. Dla przykładu \(\displaystyle{ p=q=2}\) oraz \(\displaystyle{ l=2}\) lub \(\displaystyle{ l=4}\)

Faktycznie, dzielniki muszą być różne, aby dało się utworzyć dwa równania, ale warunek różnych dzielników zawierał by się w tym, że dzielniki są względnie pierwsze.

matmatmm pisze: ↑14 wrz 2022, o 23:14 Tu przydałoby się uzasadnienie, że \(\displaystyle{ 0 \leq pr_{1}-qr_{2}+qpe < pq}\).

To, że \(\displaystyle{ 0 \leq pr_{1}-qr_{2}+qpe < pq}\) wynika wprost z tego jak e zostało zdefiniowane, jako najmniejsza liczba całkowita niemniejsza od \(\displaystyle{ \frac{ pr_{2}-qr_{1}}{qp}}\), czyli
\(\displaystyle{ e \ge\frac{ pr_{2}-qr_{1}}{qp} }\) stąd \(\displaystyle{ 0 \leq pr_{1}-qr_{2}+qpe}\). To, że \(\displaystyle{ pr_{1}-qr_{2}+qpe < pq}\) można uzasadnić z własności \(\displaystyle{ \lceil x\rceil-1<x }\).

matmatmm pisze: ↑14 wrz 2022, o 23:14 Czym są \(\displaystyle{ a}\) i \(\displaystyle{ b}\) ?

Wytłumaczę na przykładzie.
Liczba \(\displaystyle{ l}\) przy dzieleniu przez \(\displaystyle{ 81}\) daję resztę \(\displaystyle{ 2}\) oraz przy dzieleniu przez \(\displaystyle{ 17}\) daję resztę \(\displaystyle{ 7}\). Znaleźć resztę dzielenia liczby \(\displaystyle{ l}\) przez \(\displaystyle{ 1377}\).
\(\displaystyle{
l=81n+2\ \big| \cdot17 \\
l=17m+7}\)

Czy dobrze rozumiem, że dane są \(p, q, r_1\) i \(r_2\), natomiast \(l\) nie jest dane?

Jeśli \(p\) i \(q\) są względnie pierwsze, to dobieramy całkowite \(a\) i \(b\) takie, że \(ap+bq=1\). Wtedy
\(\displaystyle{ l=(ap+bq)l=ap(qm+r_2)+bq(pn+r_1) = pq(\ldots)+apr_2+bqr_1.}\)

Natomiast, jeśli \(p\) i \(q\) nie są względnie pierwsze, to pewnie nie znajdziemy reszty z dzielenia \(l\) przez \(pq\), ale możemy znaleźć resztę z dzielenia przez \(\frac{pq}{\mathrm{nwd}(p,q)}\). Robimy tak samo, tylko z równością \(a\frac{p}{\mathrm{nwd}(p,q)}+b\frac{q}{\mathrm{nwd}(p,q)}=1.\)

3a174ad9764fefcb pisze: ↑15 wrz 2022, o 22:21ale możemy znaleźć resztę z dzielenia przez \(\frac{pq}{\mathrm{nwd}(p,q)}\).

Czyli przez \(\displaystyle{ \mathrm{nww}(p, q)}\).

3a174ad9764fefcb pisze: ↑15 wrz 2022, o 22:21
Jeśli \(p\) i \(q\) są względnie pierwsze, to dobieramy całkowite \(a\) i \(b\) takie, że \(ap+bq=1\).

Potrafiłby ktoś uzasadnić, że dla dowolnych \(\displaystyle{ p,q}\) takich, że \(\displaystyle{ NWD(p,q)=1}\) istnieją takie liczby \(\displaystyle{ a,b}\), że \(\displaystyle{ ap+bq=1}\)

JK