kongruencja, podzielność liczb

marvell · Post autor: **marvell** » 30 gru 2010, o 20:22

Witam,

Mam problem z takimi oto zadaniami:

Zadanie 1. Wykorzystujac własnosci kongruencji udowodnic, ze liczba \(\displaystyle{ 7^{4n+1} + 3^{4n+1}}\) jest podzielna przez 5.

Zadanie 2. Niech a i b beda liczbami wzglednie pierwszymi. Udowodnic, ze jesli iloczyn bc jest podzielny przez a, to a jest dzielnikiem c.

Proszę o pomoc i jakieś wskazówki.

Pozdrawiam

abc666 · Post autor: **abc666** » 30 gru 2010, o 20:56

Zauważ że
\(\displaystyle{ 7^4 \equiv 1 \pmod 5}\)
oraz
\(\displaystyle{ 3^4 \equiv 1 \pmod 5}\)

marvell · Post autor: **marvell** » 30 gru 2010, o 22:04

No tak, ale nic mi to nie rozjaśnia w dalszym ciągu;)

Takie coś mi przyszło to głowy, że
mamy tak, że istnieje takie \(\displaystyle{ k}\), dla którego mamy:
\(\displaystyle{ 7^{4n}*7+3^{4n}*3=5k}\)

abc666 · Post autor: **abc666** » 30 gru 2010, o 23:32

No właśnie to masz udowodnić. Wykorzystaj to co napisałem oraz własności kongruencji.

arek1357 · Post autor: **arek1357** » 31 gru 2010, o 13:37

zapisz sobie tak:

\(\displaystyle{ (5+2)^{4n+1}+(5-2)^{4n+1}=2^{4n+1}-2^{4n+1}=0}\)-- 31 grudnia 2010, 13:38 --Oczywiście to są równości modulo

abc666 · Post autor: **abc666** » 31 gru 2010, o 14:18

Przecież wystarczy pomnożyć stronami te kongruencje odpowiednio przez 7 i a potem dodać :/

marvell · Post autor: **marvell** » 2 sty 2011, o 16:27

Mógłbym prosić o jeszcze jakąś podpowiedź? Bo w dalszym ciągu nie wiem.

A jeśli nie do tego 1 zad, to może chociaż do drugiego.

abc666 · Post autor: **abc666** » 2 sty 2011, o 17:08

abc666 pisze:Zauważ że
\(\displaystyle{ 7^4 \equiv 1 \pmod 5}\)
oraz
\(\displaystyle{ 3^4 \equiv 1 \pmod 5}\)

abc666 pisze:pomnożyć stronami te kongruencje odpowiednio przez 7 i 3 a potem dodać

(tutaj 3 mi się nie wpisała ale raczej łatwo było się domyśleć)
\(\displaystyle{ 7^4 \equiv 1 \pmod 5}\)
podnosimy stronami do n-tej potegi
\(\displaystyle{ 7^{4n} \equiv 1 \pmod 5}\) (1 do n-tej to 1)
mnożymy przez 7
\(\displaystyle{ 7^{4n+1} \equiv 7\equiv 2 \pmod 5}\)
Analogicznie z druga i dostajemy
\(\displaystyle{ 3^{4n+1}\equiv 3 \pmod 5}\)
Dodajemy
\(\displaystyle{ 7^{4n+1}+3^{4n+1} \equiv 2+3 \equiv 0 \pmod 5}\)
koniec.

marvell · Post autor: **marvell** » 2 sty 2011, o 17:42

No właśnie z tą 3 brakującą nie mogłem załapać. Dziękuję bardzo za pomoc przy pierwszym, drugie też już wiem jak zrobić.

Mam problem z jeszcze jednym, trochę z innej beczki, ale nie chcę zakładać nowych tematów:

Ile istnieje podziałow uporzadkowanych \(\displaystyle{ n}\)-elementowego zbioru \(\displaystyle{ A}\) na \(\displaystyle{ k}\) podzbiorów takich, że \(\displaystyle{ \left| A_{i}\right| = n_{i},
i=1,2,...,
k}\) i \(\displaystyle{ n= n_{1} + n_{2} + ...+n_k}\) ?

marvell · Post autor: **marvell** » 24 mar 2011, o 14:52

Witam ponownie, nie zakładam nowego tematu, ponieważ mam problem z zadaniami podobnego typu.

\(\displaystyle{ 9^{3n+1} - 3^{3n+1} \equiv 6(mod31)}\)

Jak się uporać z czymś takim ?

michary91 · Post autor: **michary91** » 24 mar 2011, o 16:06

\(\displaystyle{ 9^{3n+1} - 3^{3n+1} \equiv 6(mod31)}\)
ALe to nie jest prawda już dla \(\displaystyle{ n=1}\) , bo
\(\displaystyle{ 9^{4} - 3^{4} \equiv 1(mod31)}\)
Pozdrawiam

marvell · Post autor: **marvell** » 24 mar 2011, o 18:26

Przepraszam, źle przepisałem;D

\(\displaystyle{ 9^{3n+1} - 3^{3n+1} \equiv 6(mod13)}\)

Chodziło o taki przykład.

michary91 · Post autor: **michary91** » 24 mar 2011, o 19:26

Zauważ że:
\(\displaystyle{ 3^3 \equiv 1(mod13)}\)
i postępuj analogicznie jak powyżej