Własności kongruencji

[patricia__88]

Z jakiej własności kongruencji tutaj krzystamy:
\(\displaystyle{ 13^2 = 169 \equiv 9 \pmod{16}}\)
\(\displaystyle{ 13^4 = 169^2 \equiv 9^2 \pmod{16} = 81 \equiv1 \pmod{m}}\)
\(\displaystyle{ 13^5 = 13^4\cdot 13 \equiv 1\cdot 13 \pmod{16} \equiv 13\pmod{16}}\)

[Lorek]

Potęgowanie i mnożenie?
\(\displaystyle{ a\equiv b\pmod c\Rightarrow a^n\equiv b^n\pmod c \\
a\equiv b\pmod c\Rightarrow a\cdot d\equiv b\cdot d\pmod c}\)

[patricia__88]

Dzięki:)

-- 22 cze 2012, o 14:01 --

A czy mogę prosić o udowodnienie tych własności?-- 22 cze 2012, o 14:06 --A czy istnieje też taka własnośc, jak mnożenie konguencji, tzn.
\(\displaystyle{ a \equiv b \pmod{n}, \ c \equiv d \pmod{n} \ \Rightarrow a\cdot c \equiv b\cdot d \pmod{n}}\)?

[Lorek]

Co tu udowadniać, jak to z definicji idzie, np. potęgowanie:
\(\displaystyle{ a\equiv b\pmod c\iff c|(a-b) \Rightarrow c|\big((a-b)(a^{n-1}+a^{n-2}b+...+b^{n-1})\big) \iff\\ c|(a^n-b^n)\iff a^n\equiv b^n \pmod c}\)
mnożenie jeszcze prościej wyjdzie, bo wystarczy domnożyć w odpowiednim momencie przez \(\displaystyle{ d}\), a to co teraz dopisałaś to z mnożenia można wyprowadzić.

[patricia__88]

Nie rozumiem dlaczego tutaj możemy pomnożyć przez coś takiego:
\(\displaystyle{ c|\big((a-b)(a^{n-1}+a^{n-2}b+...+b^{n-1})\big)}\)
na pewno dobrze to zapisałeś?

[bakala12]

Tak jest ok. Skoro \(\displaystyle{ c|a-b}\) to tym bardziej \(\displaystyle{ c|(a-b) \cdot d}\) dla dowolnego d.

[patricia__88]

No dobrze, tylko że po wymnożeniu wcale nie wyjdzie nam \(\displaystyle{ a^n-b^n}\)-- 22 cze 2012, o 16:03 --Mógłby to ktoś porządnie rozpisać?

[zidan3]

No dobrze, tylko że po wymnożeniu wcale nie wyjdzie nam \(\displaystyle{ a^n-b^n}\)

Wyjdzie.

[patricia__88]

Nie no chwileczkę, jak nie wiem jak wy to liczycie, przecież
\(\displaystyle{ \sum_{i=1}^{n}a^{n-i}b^{i}=a^{n-1}b+a^{n-2}b^2+a^{n-3}b^3+...+b^n}\) a to jest różnie od tego co napisał Lorek, czyli różne od

\(\displaystyle{ (a^{n-1}+a^{n-2}b+...+b^{n-1})}\)

Natomiast wymnażając teraz otrzymamy:
\(\displaystyle{ (a-b)\left(a^{n-1}b+a^{n-2}b^2+a^{n-3}b^3+...+b^n\right)=a^nb+a^{n-1}b^2+a^{n-2}b^3+...+ab^n-a^{n-1}b^2-a^{n-2}b^3-a^{n-3}b^4-...-b^{n+1}=a^nb+ab^n-b^{n+1}}\)

-- 22 cze 2012, o 17:12 --

No widzę Zidan3 ze juz skasowałeś...?-- 22 cze 2012, o 17:15 --No ok teraz w takim razie wychodzi, jak to ludzie potrafią człowieka w błąd wprowadzić;)

[zidan3]

pomylilem sie w indesie. A wtedy nie mialem czasu poprawic, wiec usunalem.

[abc666]

\(\displaystyle{ (a-b)(a^{n-1}+a^{n-2}b+...+b^{n-1})=a^{n}+{\color{red} a^{n-1}b}+{\color{blue}a^{n-2}b^2}+...+{\color{green}ab^{n-1}}-{\color{red}a^{n-1}b}-{\color{blue}a^{n-2}b^2}-...-{\color{green}ab^{n-1}}-b^n=a^{n}-b^{n}}\)

[patricia__88]

Dzieki abc666
Czy mógłby ktoś jeszcze pokazać w ten sam sposób dowód
\(\displaystyle{ a\equiv b\pmod c\Rightarrow a\cdot d\equiv b\cdot d\pmod c}\)
i jak z tego dowodu wynika mnożenie dwóch kongruencji?

[Lorek]

Czy mógłby ktoś jeszcze pokazać w ten sam sposób dowód

bakala12 to pokazał w skrócie.

i jak z tego dowodu wynika mnożenie dwóch kongruencji?

Pomnóż \(\displaystyle{ a \equiv b \pmod{n}}\) stronami przez \(\displaystyle{ c}\), z kolei \(\displaystyle{ \ c \equiv d \pmod{n}}\) stronami przez \(\displaystyle{ b}\) i skorzystaj z przechodniości.

[patricia__88]

bakala12 to pokazał w skrócie.

Nom właśnie w skrócie, a ja niestety potrzebuję mieć to dokładnie rozpisane, mógłbyś jak nie rozwiązanie, to dać chociaż wskazówkę jak zacząć?

[Lorek]

Tak jak zacząłem z potęgami (w zasadzie cały przykład jest jak ten z potęgami): \(\displaystyle{ a\equiv b\pmod c \iff c|a-b}\) + to co napisał bakala12 + wymnożenie nawiasu + powrót do postaci z \(\displaystyle{ \pmod}\)