Podzielność przez 12

[Ponewor]

jak już masz np.:
\(\displaystyle{ 5^{4} \equiv 2 \pmod{7}}\)
i
\(\displaystyle{ 5^{20} \equiv 4 \pmod{7}}\)
wymnażasz stronami i masz:
\(\displaystyle{ 5^{24} \equiv 8 \equiv 1 \pmod{7}}\)
bez jakichś szalonych rachunków.

ewentualnie masz tylko
\(\displaystyle{ 5^{4} \equiv 2 \pmod{7}}\)
to możesz sobie podnieść to obustronnie do szóstej potęgi:
\(\displaystyle{ 5^{24} \equiv 2^{6} \equiv 64 \equiv 1 \pmod {7}}\)
nadal bez jakichś strasznych obliczeń

ale najszybciej robi się to w tabelkach tak jak np. we wzorcówce do I serii tegorocznego OMG-a.

[soulforged]

Faktycznie xD. Wracając do kongruencji - uważasz, że powinienem jeszcze poćwiczyć te kongruencje, czy poradzę już sobie na OMG? Bo II etap już 5 stycznia i nie chcę dać plamy

[Vax]

\(\displaystyle{ 1+3^n+5^n}\) ma być liczbą pierwszą, \(\displaystyle{ n=0}\) spełnia tezę, załóżmy, że \(\displaystyle{ n \ge 1}\), wówczas \(\displaystyle{ 1+3^n+5^n \ge 9}\). Rozpatrując to modulo 3 otrzymujemy \(\displaystyle{ 1+3^n+5^n \equiv 1+(-1)^n \pmod{3}}\), skąd wynika, że \(\displaystyle{ 2 \mid n \iff n = 2k}\), dla pewnej całkowitej dodatniej liczby k. Podstawiajmy i otrzymujemy \(\displaystyle{ 1+3^n+5^n = 1+9^k+25^k}\), rozpatrując to wyrażenie modulo 5 dostajemy \(\displaystyle{ 1+9^k+25^k \equiv 1+(-1)^k \pmod{5}}\), skąd \(\displaystyle{ 2 \mid k \iff k = 2l}\), rozpatrując dane wyrażenie modulo 7 dostajemy \(\displaystyle{ 1+9^{2l}+25^{2l} \equiv 1+2^{2l}+4^{2l} \equiv 1+2^{2l}+2^l \pmod{7}}\).

Teraz zauważmy, że \(\displaystyle{ 2^3 \equiv 1\pmod{7}/^d \Rightarrow 2^{3d} \equiv 1\pmod{7}}\), więc zapisując \(\displaystyle{ l = 3d+r \ , \ r \in \lbrace 0;1;2\rbrace}\) otrzymujemy \(\displaystyle{ 1+2^{2l}+2^l \equiv 1+2^{6d+2r}+2^{3d+r} \equiv 1+(2^3)^{2d}\cdot 2^{2r} + (2^3)^d\cdot 2^r \equiv 1 + 2^{2r}+2^r \pmod{7} (*)}\)

Jeżeli \(\displaystyle{ r = 1}\) to \(\displaystyle{ (*) \equiv 1+4+2 \equiv 0\pmod{7}}\) sprzeczność. Jeżeli \(\displaystyle{ r=2}\) to \(\displaystyle{ (*) \equiv 1+16+4 \equiv 0\pmod{7}}\) sprzeczność. Więc musi być \(\displaystyle{ r=0}\) skąd \(\displaystyle{ l = 3d}\) czyli \(\displaystyle{ n = 12d \iff 12 \mid n \ , \ \mathbb{QED}}\)

[soulforged]

Wytłumaczysz to ? Niewiele rozumiem...

[Ponewor]

Vax czy to aby nie to samo, tylko inaczej zapisane?

soulforged Zadań nigdy mało. A kongruencje to przydatna, a w dodatku bardzo miła rzecz. Te zadania to z 7 kwadratu? Bo jak tak, to zadanie 3. można zrobić innym sposobem. Zad. 5, 6, 7 robiłeś? Bo etykietka "OM" wcale nie oznacza, że są nierobialne w gimnazjum.

[Vax]

Jest to to, o czym pisał Ponewor tylko trochę sformalizowane.

[soulforged]

Ponewor, tak z kwadratu, a głównym powodem nierobienia tych z OM było wg mnie to, że są niemożliwe do zrobienia w gimnazjum, a czasu mam mało - raptem 13 dni, a chcę ogarnąć jeszcze indukcję, zasadę szufladkową i te nieszczęsne geometrie, które straszą swoim poziomem... Jutro spojrzę na te zadania i poświęce dzień ostatni na kongruencję. Jak znacie fajne zadanka z kongruencji poziomem podobne do OMG to możecie zapodać - jutro z rana je skrobnę.