podzielność

[wiosna]

Znajdź wszystkie \(\displaystyle{ n}\) takie, że wyrażenie \(\displaystyle{ 3 ^{n}-n}\) dzieli się przez 7.

[Maciej87]

Niech \(\displaystyle{ n=6k+r}\).
Wtedy \(\displaystyle{ 3^{6}\equiv 1 \mod 7 \Rightarrow 3^n \equiv 3^{r} \mod 7}\).
Chemy więc żeby \(\displaystyle{ n \equiv 3^{r} \mod 7}\)
Jeżeli \(\displaystyle{ r=0}\) to \(\displaystyle{ n \equiv 1 \mod 7}\) zatem \(\displaystyle{ n \equiv 36 \mod 42}\)
Jeżeli \(\displaystyle{ r=1}\) to \(\displaystyle{ n \equiv 3 \mod 7}\) zatem \(\displaystyle{ n \equiv 31 \mod 42}\)
Jeżeli \(\displaystyle{ r=2}\) to \(\displaystyle{ n \equiv 3^2 \equiv 2 \mod 7}\) zatem \(\displaystyle{ n \equiv 2 \mod 42}\)
I tak dalej.
Zadanie sprowadza się do analizy reszt \(\displaystyle{ \mod 6}\) i dobierania odpowiednich reszt \(\displaystyle{ \mod 7}\).