wykazywanie podzielności

[WesolyPierozek]

Wykaż, że istnieje nieskończenie wiele liczb naturalnych \(\displaystyle{ n}\), dla których liczba \(\displaystyle{ n^{2}+1}\) jest podzielna przez 13.

[Marcinek665]

Sprawdź, co się dzieje, gdy \(\displaystyle{ n}\) jest postaci \(\displaystyle{ 13k+5}\).

[tatteredspire]

\(\displaystyle{ 5^2\equiv -1 \pmod{13} \Rightarrow (5^{2k+1})^2\equiv -1 \pmod{13}, k \in \mathbb{N}}\)

Chyba powinienem iść spać

[WesolyPierozek]

Jeśli za n podstawie \(\displaystyle{ 13k+5}\) to wychodzi mi:
\(\displaystyle{ 169k^{2}+130k+25+1-13k=0

169k^{2}+117k+26=0}\)
to wystarczy?

Rozwiązanie tatteredspire'a nie jest dla mnie zrozumiałe do końca, wytłumaczy ktoś?

[tatteredspire]

A wiesz na czym polega modulo?

[WesolyPierozek]

Nie.
Tzn. coś tam kojarzę, ale i tak nie rozumiem całego zapisu.

[tatteredspire]

No to z modulo wynika właśnie, że \(\displaystyle{ (5^{2k+1})^2\equiv -1 \pmod{13}, k \in \mathbb{N}}\) czyli \(\displaystyle{ (5^{2k+1})^2 +1}\) jest podzielne przez \(\displaystyle{ 13}\) przy dowolnym \(\displaystyle{ k}\) naturalnym stąd istnieje nieskończenie wiele liczb \(\displaystyle{ n}\) postaci \(\displaystyle{ n=5^{2k+1}}\) takich że \(\displaystyle{ n^2+1}\) jest podzielne przez \(\displaystyle{ 13}\)

[WesolyPierozek]

Rozumiem, tylko napisz mi jeszcze skąd mam wiedzieć, że \(\displaystyle{ n=5^{2k+1}}\) Teraz widzę, że tak musi być, ale jak do tego doszedłeś?

[tatteredspire]

\(\displaystyle{ 5^2\equiv -1 \pmod{13}}\) - wychodząc z tego to zauważyłem (a to zauważyć nie trudno, bo \(\displaystyle{ 13}\) dzieli \(\displaystyle{ 26}\)). Kongruencje o tym samym module można mnożyć stronami więc pomnożywszy to \(\displaystyle{ 2k+1}\) razy stronami otrzymuję tamtą postać.

[Ponewor]

Jeśli za n podstawie \(\displaystyle{ 13k+5}\) to wychodzi mi:
\(\displaystyle{ 169k^{2}+130k+25+1-13k=0

169k^{2}+117k+26=0}\)
to wystarczy?

tak właściwie to nie wystarczy dopóki nie wyłączysz z całości 13 przed nawias

[Marcinek665]

Jeśli za n podstawie \(\displaystyle{ 13k+5}\) to wychodzi mi:
\(\displaystyle{ 169k^{2}+130k+25+1-13k=0

169k^{2}+117k+26=0}\)
to wystarczy?

Rozwiązanie tatteredspire'a nie jest dla mnie zrozumiałe do końca, wytłumaczy ktoś?

No prawie dobrze, bo to nie jest równanie i nie przyrównujesz tego do 0, tylko przekształcasz, by uzyskać oczywistą podzielność. Ale mimo wszystko zadanie jest rozwiązane, bo zauważ, że:

\(\displaystyle{ 169k^{2}+117k+26 = 13(13k^2 + 9k + 2)}\).

PS. rozwiązanie tatteredspire jest identyczne, co moje, tyle że zapisane językiem kongruencji. Nie musisz się tego uczyć, bo to w większości przypadków nie jest konieczne, a jedynie ułatwia dostrzeżenie żądanych własności.