Znajdź n dla którego ułamek jest skracalny

[Stary]

Witam,
Wiem ze to zadanie pojawiało się już pare razy ale nie za bardzo rozumiem wskazówki udzielane przez użytkowników. Zakładam nowy temat żeby nie odświeżać tych z zeszłego roku.
Prosiłbym o dość łopatologiczne wytłumaczenie, ponieważ teraz dopiero zaczynam przygode z OM.

Znajdź wszystkie liczby naturalne \(\displaystyle{ n}\), dla ktorych następujący ułamek jest skracalny:

\(\displaystyle{ \frac{111n+50}{64n+29}}\)

Wiem że były podpowiedzi z modulo, ale ich nie rozumiałem zbytnio.

[smigol]

tutaj jest całe rozwiązanie

[Stary]

Wiem że były podpowiedzi z modulo, ale ich nie rozumiałem zbytnio.

[Marcinek665]

To musisz przerobić kongruencje od podstaw, bo bez tego ani rusz.

[Stary]

Są one na jakiejś stronie internetowej? Kongruencje wykorzystywane są bardzo często przy tego typu zadaniach z dzieleniem?

[smigol]

Są one na jakiejś stronie internetowej?

Kongruencje wykorzystywane są bardzo często przy tego typu zadaniach z dzieleniem?

Owszem.

Wiem że były podpowiedzi z modulo, ale ich nie rozumiałem zbytnio.

Dałem Ci link do rozwiązania, a nie do podpowiedzi. Myślałem, że to jest jakaś różnica.

[Elvis]

Zakładam nowy temat żeby nie odświeżać tych z zeszłego roku.

Zakładam nowy temat, żeby założyć nowy temat. Tyle z tego zrozumiałem.

Ukryta treść:    

Korzystając z algorytmu Euklidesa, otrzymujemy \(\displaystyle{ (111n+50,64n+29)=(n-4,19)}\). Stąd natychmiast wynika odpowiedź, kiedy i przez co można skrócić.

[Stary]

Dałem Ci link do rozwiązania, a nie do podpowiedzi. Myślałem, że to jest jakaś różnica.

No dobrze, pomyliłem się, ale chyba nie chodzi o czepianie sie kogoś tylko o pomoc

[smigol]

Dałem Ci link do rozwiązania, a nie do podpowiedzi. Myślałem, że to jest jakaś różnica.

No dobrze, pomyliłem się, ale chyba nie chodzi o czepianie sie kogoś tylko o pomoc

Oczywiście, że nie o to chodzi. Myślałem po prostu, że trafiłeś na inny temat z tym zadaniem, w którym była tylko podpowiedź.

Pozdrawiam.

[Stary]

Rozumiem W porządku zabieram się za naukę kongruencji, dziekuje za pomoc

-- 3 lipca 2010, 17:25 --

Witam, po przestudiowaniu kongruencji już troche przejaśniała mi sytuacja z tym zadaniem. Myślę, że rozumiem już to;

\(\displaystyle{ 64n+29=0(mod p) \wedge 111n+50=0}\)
Podejrzewam, że wzięło to się stąd że \(\displaystyle{ 64n+29}\) musi podzielić się przez \(\displaystyle{ p}\) bez reszty, natomiast \(\displaystyle{ 0}\) wzięło się stąd że podzielone przez \(\displaystyle{ p}\) również da nam liczbę bez reszty (dokładnie da nam 0 ).
Następnie mamy:
\(\displaystyle{ 64 \cdot 111n+29 \cdot 111=0(mod p) \wedge 111 \cdot 64n+50 \cdot 64=0(mod p)}\)
\(\displaystyle{ 29 \cdot 111-50 \cdot 64=0 (mod p)}\)
Zatem,
\(\displaystyle{ 19=0(mod p)}\) Jako że \(\displaystyle{ 19}\) dzieli się przez samą siebie i \(\displaystyle{ p \ge 2}\) wiec \(\displaystyle{ p=19}\)
Następnie mamy \(\displaystyle{ 64n+29=0 (mod19) \wedge 111n+50=0(mod19)}\) I tutaj juz nie rozumiem następującego przejścia,
\(\displaystyle{ 7n+10=0(mod19) \wedge -3n-7=0(mod19)}\)
Prosiłbym bardzo o pomoc i cierpliwość.

[smigol]

\(\displaystyle{ 64n+29=0(mod p) \wedge 111n+50=0}\)
Podejrzewam, że wzięło to się stąd że \(\displaystyle{ 64n+29}\) musi podzielić się przez \(\displaystyle{ p}\) bez reszty, natomiast \(\displaystyle{ 0}\) wzięło się stąd że podzielone przez \(\displaystyle{ p}\) również da nam liczbę bez reszty (dokładnie da nam 0 ).

Wytłumacz to sobie tak: szukamy takiej liczby \(\displaystyle{ p \ge 2}\), dla której licznik i mianownik dzielą się bez reszty czyli liczba \(\displaystyle{ 64n+29}\) musi dawać resztę 0 z dzielenia przez \(\displaystyle{ p}\), co zapisując w języku kongruencji: \(\displaystyle{ 64n+29 \equiv 0 \ \ (mod \ p)}\). Analogicznie z mianownikiem.

Następnie mamy \(\displaystyle{ 64n+29=0 (mod19) \wedge 111n+50=0(mod19)}\) I tutaj juz nie rozumiem następującego przejścia,
\(\displaystyle{ 7n+10=0(mod19) \wedge -3n-7=0(mod19)}\)

\(\displaystyle{ 64n+29=19 \cdot 3 \cdot n + 7n+19 \cdot 1 + 10=19 \cdot (3n+1 )+7n+10}\)
Ale wiemy, że: \(\displaystyle{ 64n+29 \equiv 0 \ \ (mod \ p)}\) no to: \(\displaystyle{ 19 \cdot (3n+1 )+7n+10 \equiv 0 \ \ (mod \ p)}\),ale \(\displaystyle{ 19 \cdot (3n+1 ) \equiv 0 \ \ (mod \ p)}\) zatem musi zachodzić: \(\displaystyle{ 7n+10 \equiv 0 \ \ (mod \ p)}\).
Analogicznie z przypadkiem drugim.

[Stary]

AAAA już rozumiem, dziękuje uprzejmie!!