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

Podzielność. Reszty z dzielenia. Kongruencje. Systemy pozycyjne. Równania diofantyczne. Liczby pierwsze i względnie pierwsze. NWW i NWD.
Awatar użytkownika
Stary
Użytkownik
Użytkownik
Posty: 264
Rejestracja: 9 maja 2008, o 13:25
Płeć: Mężczyzna
Lokalizacja: Nowy Targ
Podziękował: 26 razy
Pomógł: 39 razy

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

Post autor: Stary » 2 lip 2010, o 14:18

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.

Awatar użytkownika
smigol
Korepetytor
Korepetytor
Posty: 3454
Rejestracja: 20 paź 2007, o 23:10
Płeć: Mężczyzna
Lokalizacja: Warszawa
Podziękował: 89 razy
Pomógł: 353 razy

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

Post autor: smigol » 2 lip 2010, o 14:37


Awatar użytkownika
Stary
Użytkownik
Użytkownik
Posty: 264
Rejestracja: 9 maja 2008, o 13:25
Płeć: Mężczyzna
Lokalizacja: Nowy Targ
Podziękował: 26 razy
Pomógł: 39 razy

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

Post autor: Stary » 2 lip 2010, o 14:44

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

Marcinek665
Korepetytor
Korepetytor
Posty: 1824
Rejestracja: 11 sty 2007, o 20:12
Płeć: Mężczyzna
Lokalizacja: Katowice, Warszawa
Podziękował: 73 razy
Pomógł: 228 razy

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

Post autor: Marcinek665 » 2 lip 2010, o 14:49

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

Awatar użytkownika
Stary
Użytkownik
Użytkownik
Posty: 264
Rejestracja: 9 maja 2008, o 13:25
Płeć: Mężczyzna
Lokalizacja: Nowy Targ
Podziękował: 26 razy
Pomógł: 39 razy

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

Post autor: Stary » 2 lip 2010, o 15:01

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

Awatar użytkownika
smigol
Korepetytor
Korepetytor
Posty: 3454
Rejestracja: 20 paź 2007, o 23:10
Płeć: Mężczyzna
Lokalizacja: Warszawa
Podziękował: 89 razy
Pomógł: 353 razy

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

Post autor: smigol » 2 lip 2010, o 15:14

Stary pisze:Są one na jakiejś stronie internetowej?
http://lmgtfy.com/?q=kongruencje
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.

Awatar użytkownika
Elvis
Użytkownik
Użytkownik
Posty: 756
Rejestracja: 17 paź 2004, o 18:09
Płeć: Mężczyzna
Lokalizacja: Warszawa
Podziękował: 1 raz
Pomógł: 84 razy

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

Post autor: Elvis » 2 lip 2010, o 16:12

Stary pisze: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ść:    

Awatar użytkownika
Stary
Użytkownik
Użytkownik
Posty: 264
Rejestracja: 9 maja 2008, o 13:25
Płeć: Mężczyzna
Lokalizacja: Nowy Targ
Podziękował: 26 razy
Pomógł: 39 razy

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

Post autor: Stary » 2 lip 2010, o 16:56

smigol pisze: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

Awatar użytkownika
smigol
Korepetytor
Korepetytor
Posty: 3454
Rejestracja: 20 paź 2007, o 23:10
Płeć: Mężczyzna
Lokalizacja: Warszawa
Podziękował: 89 razy
Pomógł: 353 razy

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

Post autor: smigol » 2 lip 2010, o 17:39

Stary pisze:
smigol pisze: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.

Awatar użytkownika
Stary
Użytkownik
Użytkownik
Posty: 264
Rejestracja: 9 maja 2008, o 13:25
Płeć: Mężczyzna
Lokalizacja: Nowy Targ
Podziękował: 26 razy
Pomógł: 39 razy

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

Post autor: Stary » 2 lip 2010, o 20:28

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ść.

Awatar użytkownika
smigol
Korepetytor
Korepetytor
Posty: 3454
Rejestracja: 20 paź 2007, o 23:10
Płeć: Mężczyzna
Lokalizacja: Warszawa
Podziękował: 89 razy
Pomógł: 353 razy

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

Post autor: smigol » 3 lip 2010, o 19:21

Stary pisze: \(\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.

Awatar użytkownika
Stary
Użytkownik
Użytkownik
Posty: 264
Rejestracja: 9 maja 2008, o 13:25
Płeć: Mężczyzna
Lokalizacja: Nowy Targ
Podziękował: 26 razy
Pomógł: 39 razy

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

Post autor: Stary » 3 lip 2010, o 19:23

AAAA już rozumiem, dziękuje uprzejmie!!

ODPOWIEDZ