Ciekawy problem z kongruencją

Podzielność. Reszty z dzielenia. Kongruencje. Systemy pozycyjne. Równania diofantyczne. Liczby pierwsze i względnie pierwsze. NWW i NWD.
realityoppa
Użytkownik
Użytkownik
Posty: 117
Rejestracja: 26 gru 2012, o 16:36
Płeć: Mężczyzna
Lokalizacja: Kraków
Podziękował: 54 razy
Pomógł: 10 razy

Ciekawy problem z kongruencją

Post autor: realityoppa » 27 lip 2013, o 23:01

Jaka musi być zależność między całkowitymi dodatnimi liczbami \(\displaystyle{ a}\) i \(\displaystyle{ b}\), aby nie istniało takie naturalne \(\displaystyle{ n}\) że: \(\displaystyle{ a^{n}\equiv1 (mod}\) \(\displaystyle{ b)}\).
Oczywiście \(\displaystyle{ n\ge2}\)
Rekrutacja Instytut Matematyczny, Uniwersytet Wrocławski (gif)

Awatar użytkownika
Vax
Użytkownik
Użytkownik
Posty: 2913
Rejestracja: 27 kwie 2010, o 22:07
Płeć: Mężczyzna
Lokalizacja: Biała Podlaska / Warszawa
Podziękował: 4 razy
Pomógł: 611 razy

Ciekawy problem z kongruencją

Post autor: Vax » 27 lip 2013, o 23:09

\(\displaystyle{ (a,b)=1}\)

Awatar użytkownika
ares41
Gość Specjalny
Gość Specjalny
Posty: 6499
Rejestracja: 19 sie 2010, o 08:07
Płeć: Mężczyzna
Lokalizacja: Kraków
Podziękował: 142 razy
Pomógł: 922 razy

Ciekawy problem z kongruencją

Post autor: ares41 » 27 lip 2013, o 23:19

Hmh...
\(\displaystyle{ a=2 \\ b=3\\(2,3)=1\\ 2^2\equiv 1 \pmod{3}}\)
Czyli istnieje takie \(\displaystyle{ n}\) mimo, że \(\displaystyle{ (a,b)=1}\)

Awatar użytkownika
Vax
Użytkownik
Użytkownik
Posty: 2913
Rejestracja: 27 kwie 2010, o 22:07
Płeć: Mężczyzna
Lokalizacja: Biała Podlaska / Warszawa
Podziękował: 4 razy
Pomógł: 611 razy

Ciekawy problem z kongruencją

Post autor: Vax » 27 lip 2013, o 23:26

A dobra przeczytałem istniało No to \(\displaystyle{ (a,b) \neq 1}\)

realityoppa
Użytkownik
Użytkownik
Posty: 117
Rejestracja: 26 gru 2012, o 16:36
Płeć: Mężczyzna
Lokalizacja: Kraków
Podziękował: 54 razy
Pomógł: 10 razy

Ciekawy problem z kongruencją

Post autor: realityoppa » 28 lip 2013, o 10:49

Dzięki za warunek, a mógłbyś mi to jakoś uzasadnić ?

Awatar użytkownika
Vax
Użytkownik
Użytkownik
Posty: 2913
Rejestracja: 27 kwie 2010, o 22:07
Płeć: Mężczyzna
Lokalizacja: Biała Podlaska / Warszawa
Podziękował: 4 razy
Pomógł: 611 razy

Ciekawy problem z kongruencją

Post autor: Vax » 28 lip 2013, o 11:03

Jeżeli \(\displaystyle{ (a,b)=1}\) to istnieje takie \(\displaystyle{ n}\), wystarczy przyjąć \(\displaystyle{ n=\phi(b)}\) (twierdzenie Eulera), a jeżeli \(\displaystyle{ (a,b) \neq 1}\), to zakładając nie wprost, że istnieje takie \(\displaystyle{ n}\), bierzemy dowolną liczbę pierwszą \(\displaystyle{ p \mid (a,b)}\), wówczas \(\displaystyle{ a^n \equiv 1\pmod{b} \Rightarrow a^n \equiv 1\pmod{p} \Rightarrow 0 \equiv 1\pmod{p}}\)

sprzeczność.

ODPOWIEDZ