Układ kongurencji

[Kanodelo]

W sadzie zebrano jabłka, których nie było wiecej niz 1000.

Gdyby podzielic jabłka równo do 7 koszy, to zostanie 1 jabłko.

Gdyby podzielic jabłka równo do 13 koszy, to zostanie 6 jabłek.

Mozna jednak podzielic jabłka równo na 11 cz¸esci. Ile zebrano

jabłek?

Tu trzeba jakis układ kongurencji ułożyć.... Ale niemam pojęcia jak Pomożcie....

[norwimaj]

\(\displaystyle{ \begin{cases}
x\equiv1\pmod7\\
x\equiv6\pmod{13}\\
x\equiv0\pmod{11}\\
0\le x\le1000
\end{cases}}\)

[Kanodelo]

Czyli z pierwszego \(\displaystyle{ x=7k+1}\)

wstawiam do drugiej i jest \(\displaystyle{ 7k+1 =6(mod 13)}\)
I teraz żeby zostało samo 7k trzeba odjąć 12?

[norwimaj]

No, jeśli nie znasz lepszej metody, to może Ci się tak uda. Nie uczono Cię o rozwiązywaniu układów a wymagają tego od Ciebie?

[Kanodelo]

Ja sie sam tego uczę, nie miałem tego w szkole nigdy

[norwimaj]

Chcemy rozwiązać układ
\(\displaystyle{ \begin{cases}
x\equiv a_1\pmod{p_1}\\
x\equiv a_2\pmod{p_2}\\
\ldots\\
x\equiv a_n\pmod{p_n}
\end{cases}}\)

gdzie liczby \(\displaystyle{ p_1,\ldots,p_n}\) są względnie pierwsze.

Niech \(\displaystyle{ P=p_1p_2\ldots p_n}\). Niech \(\displaystyle{ m_i}\) to będzie odwrotność do \(\displaystyle{ \frac{P}{p_i}}\) modulo \(\displaystyle{ p_i}\). Możemy ją znaleźć algorytmem Euklidesa. Rozwiązaniem układu jest

\(\displaystyle{ a_1m_1\frac{P}{p_1}+\ldots+a_nm_n\frac{P}{p_n}}\).

Z Chińskiego Twierdzenia o Resztach wiadomo, że jest to jedyne rozwiązanie tego układu modulo \(\displaystyle{ P}\).

[Kanodelo]

\(\displaystyle{ \begin{cases}
x\equiv1\pmod7\\
x\equiv6\pmod{13}\\
x\equiv0\pmod{11}\\
0\le x\le1000
\end{cases}}\)

No dobra to na przykładzie tego układu to będzie:
\(\displaystyle{ P=1001}\) i teraz \(\displaystyle{ p_3=11}\) więc \(\displaystyle{ \frac{P}{p_i}=91}\), ale to się dzieli bez reszty, podobnie \(\displaystyle{ p_2=13}\) i \(\displaystyle{ \frac{P}{p_2}=77}\) reszta 0, a \(\displaystyle{ \frac{1001}{7}}\)też się dzieli bez restzy
i teraz elementy odwrotne trzeba wyznaczyc, i podstawic do wzoru

[norwimaj]

Od razu zauważ, że \(\displaystyle{ m_3}\) nie musisz wyznaczać, bo i tak je pomnożysz przez \(\displaystyle{ 0}\).

[Kanodelo]

ZACZYNAM COŚ KUMAĆ
DZIEKI :D