Kongurencja/kongurencja kwadratowa

Podzielność. Reszty z dzielenia. Kongruencje. Systemy pozycyjne. Równania diofantyczne. Liczby pierwsze i względnie pierwsze. NWW i NWD.
justdzo
Użytkownik
Użytkownik
Posty: 54
Rejestracja: 27 paź 2015, o 19:57
Płeć: Kobieta
Lokalizacja: Warszawa

Kongurencja/kongurencja kwadratowa

Post autor: justdzo »

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 :)
PoweredDragon
Użytkownik
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

Post autor: PoweredDragon »

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ć)
Awatar użytkownika
Premislav
Użytkownik
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

Post autor: Premislav »

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?
justdzo
Użytkownik
Użytkownik
Posty: 54
Rejestracja: 27 paź 2015, o 19:57
Płeć: Kobieta
Lokalizacja: Warszawa

Kongurencja/kongurencja kwadratowa

Post autor: justdzo »

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ć)
Dzięki za odpowiedź.
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.
PoweredDragon
Użytkownik
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

Post autor: PoweredDragon »

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 :D Nie mam, niestety, innego pomysłu.
ODPOWIEDZ