множеството от най-големите ощи делители на н^2+к и (н+1)^2+

[1089]

Докажете или опровергайте: множеството от най-големите ощи делители на н^2+к и (н+1)^2+к за дадено естествено к и н пробягващо всички естесвени числа съвпада с множеството oт делителите на 4к+1.

[mkmarinov]

Ако го напишеш така, че да се разбира условието, цена няма да имаш.

[1089]

dadeno e estestveno 4islo k i proizvolno estestveno n. d e nai golqm ob6t delitel na n^2+k i (n+1)^2+k togava i samo togava kogato d deli 4k+1

[allier]

Едната посока е лесна. Ако d дели и двете, то d/2n+1, значи n дава остатък -0.5 при деление на d. Заместваме, [tex]n^2+k[/tex] дава остатък [tex]k+0.25[/tex] което трябва да е 0-ла, значи d дели 4k+1. За другата посока, избираме 2n+1=d и проверяваме, че d дели и двете (значи е точно НОД-а).

[1089]

moje li pak da obqsni6 vtoroto?

[allier]

[tex](n+1)^2+k = n^2+k+(2n+1)[/tex]. Ако [tex]d=2n+1[/tex], то НОД на [tex]n^2+k[/tex] и [tex](n+1)^2+k[/tex] дели d. Остава да докажем, че d дели НОД-а, откъдето ще следва, че НОД=d. За тази цел правим следното:
[tex]n^2+k = (-0.5)^2+k=k+0.25=\frac{4k+1}{4 }=0(mod d)[/tex], тъй като d беше произволно избран делител на 4k+1. Значи, [tex]d/n^2+k[/tex]. Оттук следва, че d/НОД.

P.S. [tex]n^2 = (\frac{d-1}{2 })^2 = (-0.5)^2 (mod d)[/tex]