Stranezza sovietivca del \'78

[sprmnt21]

fra i problemi che si trovano a:
<BR>
<BR>http://www.kalva.demon.co.uk/soviet/sov78.html
<BR>il seguente, nel modo in cui e\' formulato, non mi convince del tutto.
<BR>
<BR>
<BR>7. Let p(x) = x2 + x + 1. Show that for every positive integer n, the numbers n, p(n), p(p(n)), p(p(p(n))), ... are relatively prime.
<BR>
<BR>
<BR>
<BR>
<BR>Se si deve intendere che due qualsiasi numeri della successione sono coprimi, allora la tesi, secondo me, e\' sbagliata.
<BR>
<BR>Se invece ci si riferisce solo a coppie di numeri contigui nella successione, allora e\' troppo semplice.
<BR>
<BR>
<BR>Che ne pensate?
<BR>
<BR>
<BR>

[ReKaio]

sui numeri contigui parrebbe troppo facile, l\'esercizio me lo ricordo, l\'avevo dimostrato tempo addietro, funzionava

[pennywis3]

Tempo fa in questo sito era possibile scaricare una mega raccolta di problemi russi, e mi ricordo che c\'era anche questo, ed io avevo avuto i tuoi stessi dubbi, quindi credo proprio che sia sbagliato un segno, magari è x^2 - x +1... anche perchè sennò 3 e p(p(3)) non sono coprimi....

[sprmnt21]

Infatti e\' quello che risulta anche a me. E nel caso di x^2-x+1 la tesi, secondo te, e\' sostenibile?
<BR>
<BR>l\'hai provata o e\' solo una congettura?
<BR>
<BR>

[pennywis3]

No, questa non è una congettura, è dimostrabile abbastanza facilmente.... se vuoi la soluzione dimmelo e la posto subito.
<BR>
<BR>Ciaps
<BR>
<BR>~p3~

[ma_go]

beh, direi che questo problemino è proprio simpatico!
<BR>dunque, se a nessuno dà fastidio, io posterei anche la soluzione...
<BR>naturalmente, chi non volesse leggerla non è obbligato a farlo, quindi non mi incolpate di postare troppo presto e di non lasciarvi il tempo per farveli da voi...
<BR>
<BR>dunque dunque...
<BR>sia f(f(...f(n))..) (con f( ripetuto m volte) f_m(n).
<BR>(per chi non lo sapesse) teorema di bezout:
<BR>MCD(a,b)=1 <=> esiste almeno una coppia (h,k)€Z² tale che ha+kb=1.
<BR>ora, risulta che MCD(h,b)=MCD(k,a)=1 (si dimostra facilmente per assurdo, ma non voglio essere troppo pedante)
<BR>supponiamo ora per induzione (estesa) su m che f_m(n) sia primo con tutti gli f_i(n) (0<=i<=m.) per ogni 0<=m<=p, e in particolare che h sia 1.
<BR>ovviamente f_0(n) e f_1(n) sono primi tra loro, e h nell\'espressione del teorema di bezout è 1. quindi il primo dei due requisiti per l\'induzione c\'è.
<BR>per ipotesi induttiva abbiamo che f_p(n) è primo con tutti gli f_i(n) (0<=i<=m.), quindi per il teorema di bezout esiste una coppia tale che f_m(n)+k*f_i(n)=1, quindi f_i(n)|(h*f_m(n)-1).
<BR>ma allora,a poiché f_(p+1)(n) = f_p(n)^2-f_p(n)+1,
<BR>1 = f_(p+1)(n)-f_p(n)^2+f_p(n) = f_(p+1)(n)-f_p(n)(1-f_p(n)), quindi f_(p+1)(n) è primo con f_p(n), ma poichè f_i(n) divide (1-f_p(n)), è primo anche con ogni f_i(n).
<BR>quindi la tesi è vera.
<BR> cvd...
<BR>
<BR>ps. fregato! <IMG SRC="images/forum/icons/icon_razz.gif"> <IMG SRC="images/forum/icons/icon_biggrin.gif">
<BR>pps. e con oggi sono 17 gli anni buttati al vento!

[XT]

davvero? be\' che dire, auguri! <IMG SRC="images/forum/icons/icon_wink.gif">

[Fede_HistPop]

Tanti auguri, ma_go!!