Hej, potrzebuje pomocy w dwóch poniższych zadaniach:
1. Wyznacz wszystkie liczby pierwsze \(\displaystyle{ p<100}\) takie, że kongurencja \(\displaystyle{ X^{2} \equiv 10\pmod{p}}\) ma rozwiązania.
Nie wiem czy dobrze myśle - należy skorzystać z symbolu Lagrande'a?
2. Wykaż, że zbiór \(\displaystyle{ \{p \in P: p \not\equiv 1\pmod{8}\}}\)jest nieskończony.
Bardzo proszę o nakierowanie bądź rozwiązania
Kongurencja/kongurencja kwadratowa
-
- Użytkownik
- Posty: 817
- Rejestracja: 19 lis 2016, o 23:48
- Płeć: Mężczyzna
- wiek: 21
- Lokalizacja: Polska
- Podziękował: 3 razy
- Pomógł: 115 razy
Kongurencja/kongurencja kwadratowa
1. Kongruencja! Tak jak robi Gołomp
2. Symbol Legendre'a
W zadaniu 1. Korzystasz z symbolu Legendre'a jako funkcji wykładniczej przy podstawie 10.
2.
Poczytaj o wariacji Erdősa (Nie mam innego pomysłu - jak na coś wpadnę to dam znać)
2. Symbol Legendre'a
W zadaniu 1. Korzystasz z symbolu Legendre'a jako funkcji wykładniczej przy podstawie 10.
2.
Poczytaj o wariacji Erdősa (Nie mam innego pomysłu - jak na coś wpadnę to dam znać)
- Premislav
- Użytkownik
- Posty: 15685
- Rejestracja: 17 sie 2012, o 13:12
- Płeć: Mężczyzna
- Lokalizacja: Warszawa
- Podziękował: 195 razy
- Pomógł: 5219 razy
Kongurencja/kongurencja kwadratowa
2. Moja propozycja:
łatwo widać, że wystarczy pokazać, iż jest nieskończenie wiele liczb pierwszych postaci \(\displaystyle{ 4k+3}\) (one nie dają reszty \(\displaystyle{ 1}\) modulo \(\displaystyle{ 4}\), więc tym bardziej modulo \(\displaystyle{ 8}\)), ale wygodniej będzie zapisać \(\displaystyle{ 4k-1}\) (oczywiście \(\displaystyle{ k}\) całkowite).
Dowód może przebiegać podobnie jak dowód Euklidesa na istnienie nieskończenie wielu liczb pierwszych.
Und zwar:
przypuśćmy nie wprost, że liczby \(\displaystyle{ p_1=4k_1-1, \ p_2=4k_2-1, \ldots p_n=4k_n-1}\) są wszystkimi istniejącymi liczbami pierwszymi postaci \(\displaystyle{ 4k-1}\).
Rozważmy liczbę
\(\displaystyle{ 4\cdot \prod_{i=1}^{n} (4k_i-1)-1}\)
Jest ona nieparzysta, względnie pierwsza z liczbami \(\displaystyle{ p_1\ldots p_n}\) i ma pewien dzielnik pierwszy postaci \(\displaystyle{ 4m-1}\) (to trzeba pokazać, lecz nie jest to super skomplikowane, wręcz przeciwnie). Wniosek?
łatwo widać, że wystarczy pokazać, iż jest nieskończenie wiele liczb pierwszych postaci \(\displaystyle{ 4k+3}\) (one nie dają reszty \(\displaystyle{ 1}\) modulo \(\displaystyle{ 4}\), więc tym bardziej modulo \(\displaystyle{ 8}\)), ale wygodniej będzie zapisać \(\displaystyle{ 4k-1}\) (oczywiście \(\displaystyle{ k}\) całkowite).
Dowód może przebiegać podobnie jak dowód Euklidesa na istnienie nieskończenie wielu liczb pierwszych.
Und zwar:
przypuśćmy nie wprost, że liczby \(\displaystyle{ p_1=4k_1-1, \ p_2=4k_2-1, \ldots p_n=4k_n-1}\) są wszystkimi istniejącymi liczbami pierwszymi postaci \(\displaystyle{ 4k-1}\).
Rozważmy liczbę
\(\displaystyle{ 4\cdot \prod_{i=1}^{n} (4k_i-1)-1}\)
Jest ona nieparzysta, względnie pierwsza z liczbami \(\displaystyle{ p_1\ldots p_n}\) i ma pewien dzielnik pierwszy postaci \(\displaystyle{ 4m-1}\) (to trzeba pokazać, lecz nie jest to super skomplikowane, wręcz przeciwnie). Wniosek?
Kongurencja/kongurencja kwadratowa
Dzięki za odpowiedź.PoweredDragon pisze:1. Kongruencja! Tak jak robi Gołomp
2. Symbol Legendre'a
W zadaniu 1. Korzystasz z symbolu Legendre'a jako funkcji wykładniczej przy podstawie 10.
2.
Poczytaj o wariacji Erdősa (Nie mam innego pomysłu - jak na coś wpadnę to dam znać)
Móglbyś mi troche rozjaśnić z tym symbolem Legendre'a ?
Bo nie bardzo wiem jak to ugryźć.
Ostatnio zmieniony 10 kwie 2018, o 23:11 przez Jan Kraszewski, łącznie zmieniany 1 raz.
Powód: Przepisuj nazwiska uważniej.
Powód: Przepisuj nazwiska uważniej.
-
- Użytkownik
- Posty: 817
- Rejestracja: 19 lis 2016, o 23:48
- Płeć: Mężczyzna
- wiek: 21
- Lokalizacja: Polska
- Podziękował: 3 razy
- Pomógł: 115 razy
Re: Kongurencja/kongurencja kwadratowa
Symbol Legendre'a to zwykła funkcja.
\(\displaystyle{ \left( \frac{a}{p}\right) = a^{\frac{p-1}{2}} \pmod p}\), gdzie \(\displaystyle{ p}\) jest liczbą pierwszą. Jeśli jego wartość wynosi \(\displaystyle{ 1}\), to kongruencja \(\displaystyle{ x^2 \equiv a \pmod p}\) ma rozwiązanie, \(\displaystyle{ -1}\) jeśli nie ma rozwiązań, \(\displaystyle{ 0}\), gdy \(\displaystyle{ p \mid a}\)
Tutaj warto też skorzystać z faktu, że \(\displaystyle{ \left( \frac{ab}{p}\right) =\left( \frac{b}{p}\right) \left( \frac{a}{p}\right)}\)
Robisz dla \(\displaystyle{ a = 10}\), może zauważysz wzór, a jak nie to na piechotę. Mało tych liczb pierwszych jest tak czy siak Nie mam, niestety, innego pomysłu.
\(\displaystyle{ \left( \frac{a}{p}\right) = a^{\frac{p-1}{2}} \pmod p}\), gdzie \(\displaystyle{ p}\) jest liczbą pierwszą. Jeśli jego wartość wynosi \(\displaystyle{ 1}\), to kongruencja \(\displaystyle{ x^2 \equiv a \pmod p}\) ma rozwiązanie, \(\displaystyle{ -1}\) jeśli nie ma rozwiązań, \(\displaystyle{ 0}\), gdy \(\displaystyle{ p \mid a}\)
Tutaj warto też skorzystać z faktu, że \(\displaystyle{ \left( \frac{ab}{p}\right) =\left( \frac{b}{p}\right) \left( \frac{a}{p}\right)}\)
Robisz dla \(\displaystyle{ a = 10}\), może zauważysz wzór, a jak nie to na piechotę. Mało tych liczb pierwszych jest tak czy siak Nie mam, niestety, innego pomysłu.