Matematické Fórum

stuart clark · 02. 05. 2013 03:34

If $f(n)= n^2+20$ and $d$ to be the greatest common divisor of $f(n)$ and $f(n+1)$

Then how can i Prove $d$ divides $81$ .

BakyX · 02. 05. 2013 15:12

Autor skryl část textu. Zobrazit/skrýt!

check_drummer · 02. 05. 2013 18:10

↑ BakyX:
Ahoj, pěkné řešení. Jak jsi k němu dospěl? Zkoušel jsi hledat vhoné lineární členy v proměnné n, kterými vynásobit f(n) a f(n+1) tak, aby po odečtení těchto součinů výsledná hodnota byla kosntanta, a nebo jsi použil nějaký jiný postup? Děkuji.

vanok · 02. 05. 2013 21:48

Ahoj ↑ check_drummer:,
Tu kolega ↑ check_drummer: pouzil Bézout-ovu teoremu.
http://en.wikipedia.org/wiki/B%C3%A9zout%27s_identity
( presnejsie ide o teoremu Bachet-Bézout)
http://fr.wikipedia.org/wiki/Th%C3%A9or … %C3%A9zout

check_drummer · 02. 05. 2013 21:55

↑ vanok:
Ale obávám se, že Bezoutova věta sama o sobě k nalezení 2n+3 a -(2n-1) nepomůže - k tomu by se hodil spíš Eukleidův algoritmus.

vanok · 02. 05. 2013 22:19

↑ check_drummer:,
Podla mna citovana teorema riesi dany problem.
Ak ide o algoritmus hladania vhodnych koeficientov v pouzitej identite, tak nemozem odpovedat za kolegu ako postupoval.( Ale v dokaze Bezout-ovej teoremy sa da pouzit rozsireny Euklidov algoritmus).

BakyX · 02. 05. 2013 23:15

Osobne som išiel na tie koeficienty takto:

$d$ delí $f(n+1)-f(n)=2n+1$ .

Preto $d$ delí aj $2n^2+n$ , preto delí aj $2(n^2+20)-(2n^2+n)=40-n$ ,

preto delí aj $2(40-n)=80-2n$ , preto delí aj $(80-2n)+(2n+1)=81$

A potom to dal dokopy cez $f(n), f(n+1)$ a tak našiel tie koeficienty :D

Pavel Brožek

Já jsem postupoval asi celkem podobně jako BakyX. Používal jsem následující úpravy (které samozřejmě platí i v druhém argumentu):

1) Platí $\gcd(a,b)=\gcd(a+kb, b)$ , kde k je celé číslo.
2) Pokud je c nesoudělné s b, pak $gcd(a,b)=gcd(ac,b)$ .

Pak už to bylo celkem jednoduché:

$\gcd(f(n),f(n+1))&=\gcd(n^2+20, n^2+2n+21)=\\ &=\gcd(n^2+20, n^2+2n+21-(n^2+20))=\\ &=\gcd(n^2+20, 2n+1)=\\ &=\gcd(2\cdot(n^2+20), 2n+1)=\\ &=\gcd(2n^2+40, 2n+1)=\\ &=\gcd(2n^2+40-n\cdot(2n+1), 2n+1)=\\ &=\gcd(40-n, 2n+1)=\\ &=\gcd(40-n, 2n+1+2(40-n))=\\ &=\gcd(40-n,81)$

A tím jsem skončil, protože je jasné, že $\gcd(40-n,81)|81$ . Koeficienty by se daly asi získat nějak rozšířením rozšířeného Euklidova algoritmu, o to už jsem se nepokoušel :).

check_drummer · 03. 05. 2013 18:16

Já jsem to zkusil Eukleidovým algoritmem (použitý pro důkaz Bezoutovy věty) a získal jsem, že:
f(n+1).(-n/2+1/4)+f(n).(n/2-3/4)=81/4. Takže po vynásobení 4 máme již několikrát citované:
f(n+1).(-2n+1)+f(n)(2n-3)=81.

stuart clark · 07. 05. 2013 04:39

Thanks Friends

Matematické Fórum

#1 02. 05. 2013 03:34

greatest common diviser

#2 02. 05. 2013 15:12

Re: greatest common diviser

#3 02. 05. 2013 18:10

Re: greatest common diviser

#4 02. 05. 2013 21:48

Re: greatest common diviser

#5 02. 05. 2013 21:55

Re: greatest common diviser

#6 02. 05. 2013 22:19

Re: greatest common diviser

#7 02. 05. 2013 23:15

Re: greatest common diviser

#8 03. 05. 2013 09:27 — Editoval Pavel Brožek (03. 05. 2013 09:27)

Re: greatest common diviser

#9 03. 05. 2013 18:16

Re: greatest common diviser

#10 07. 05. 2013 04:39

Re: greatest common diviser

Zápatí