Podzielność liczb

[anna_]

-- dzisiaj, o 20:00 --

Już widzę, mój bład, źle tłumaczę.

[klaustrofob]

słusznie Zordonie, mój "dowód" nie jest poprawny. na ogół wskazane przez Ciebie podzielności, które potem chciała uzasadnić nmn są nieprawdziwe. przepraszam

[gelo21]

To ja już nie wiem jak to zrobić

[klaustrofob]

ja też nie (jeszcze?). gdyby n było liczbą pierwszą, to moje rozumowanie przechodzi, bo z faktu, że \(\displaystyle{ n|a^n-b^n}\) da się wtedy wywnioskować, że \(\displaystyle{ n|a-b}\)

[gelo21]

Tylko co dalej ?

[eufiga5]

\(\displaystyle{ n|(a^n -b^n) \Rightarrow \exists\limits_{k} (a^n - b^n) = k n \Rightarrow \frac{(a^n-b^n)}{(a-b)} = \frac{kn}{a-b} = n \frac{k}{a-b}}\)

[smigol]

To jeszcze pokaż, że \(\displaystyle{ \frac{k}{a-b} \in \mathbb{Z}}\)

Co do zadania: Jeśli \(\displaystyle{ a^n \equiv b^n \pmod n}\), to \(\displaystyle{ a \equiv b \pmod n}\) (w zasadzie tu jest równoważność).
Weźmy \(\displaystyle{ a=a_1n+r_1}\), \(\displaystyle{ b=b_1n+r_2}\). Oczywiście \(\displaystyle{ 0 \le r_1,r_2<n}\), mamy: \(\displaystyle{ a^n \equiv r_1^n \pmod n}\) ( z dwumianu Newtona) i \(\displaystyle{ b^n \equiv r_2^n \pmod n}\), zatem jeśli \(\displaystyle{ a^n \equiv b^n \pmod n}\), to \(\displaystyle{ r_1^n \equiv r_2^n \pmod n}\), a skoro \(\displaystyle{ 0 \le r_1,r_2<n}\), to \(\displaystyle{ r_1=r_2}\), czyli \(\displaystyle{ a \equiv b \pmod n}\).

[marcinz]

Co do zadania: Jeśli \(\displaystyle{ a^n \equiv b^n \pmod n}\), to \(\displaystyle{ a \equiv b \pmod n}\) (w zasadzie tu jest równoważność).

Wydaje mi się, że ta implikacja nie zachodzi. O ile nie pomyliłem się w rachunkach to biorąc a=3,b=1,n=8 dostajemy \(\displaystyle{ a^n \equiv b^n \pmod n}\).

[gelo21]

Ok jeśli już wiem ze a przystaje do b to co dalej?

[smigol]

marcinz, \(\displaystyle{ 3^8=6561}\), oraz \(\displaystyle{ 8|6561-1}\), więc \(\displaystyle{ 3^8 \equiv 1 \pmod 8}\) no i oczywiście \(\displaystyle{ 1^8 \equiv 1 \pmod 8}\).

gelo21, dalej sjkorzystaj z tego wzoru, o którym wspominałem, masz n wyrażeń w jednym z nawiasów.

[gelo21]

Smigol mógłbyś to rozpisać??

[smigol]

\(\displaystyle{ a^{n-1}+a^{n-2}b+a^{n-3}b^2+...+a^2b^{n-3}+ab^{n-2}+b^{n-1} \equiv a^{n-1}+a^{n-2}a+a^{n-3}a^2+...+a^2a^{n-3}+aa^{n-2}+a^{n-1} \equiv na^{n-1} \equiv 0 \pmod n}\)

[Qń]

marcinz, \(\displaystyle{ 3^8=6561}\), oraz \(\displaystyle{ 8|6561-1}\), więc \(\displaystyle{ 3^8 \equiv 1 \pmod 8}\) no i oczywiście \(\displaystyle{ 1^8 \equiv 1 \pmod 8}\)

Przyjrzyj się jeszcze raz (prawidłowemu) kontrprzykładowi Marcina.

Q.

[klaustrofob]

smigolu: \(\displaystyle{ 3^4\equiv 1^4\ (\mathrm{mod}\ 4)}\), ale nieprawdą jest, że \(\displaystyle{ 3\equiv 1\ (\mathrm{mod}\ 4)}\). Twój dowód tego, że \(\displaystyle{ a^n\equiv b^n \Rightarrow a\equiv b}\) jest "dowodem", a sypie się tu:

\(\displaystyle{ r_1^n \equiv r_2^n \pmod n}\), a skoro \(\displaystyle{ 0 \le r_1,r_2<n}\), to \(\displaystyle{ r_1=r_2}\) (...)

[smigol]

No tak, sorry. Nie wiem co mi strzeliło do łba ;d