Pagina 1 di 1

"Aritmetica russa" - 6. Funzioni di funzioni

Inviato: mer set 13, 2006 7:49 pm
da Admin
Admin ha scritto:Dalla sezione "Aritmetica russa"
Funzioni di funzioni

Sia f(x) = x2 + x + 1.
Dimostrare che per ogni numero naturale m>1 i numeri m, f(m), f(f(m)), ... sono primi fra loro.
(Tashkent, 1978)
Dunque, basta dimostrare che m e f(m) sono primi tra loro;
dopo di che è ovvio che anche f(m) e f(f(m)) sono primi tra loro;
se poi la traccia intende che tutti i numeri m, f(m), f(f(m)), ... devono essere primi tra loro, ossia che tutti non abbiano alcun divisore in comune >1, a maggior ragione basta solo dimostrare che m e f(m) sono primi tra loro.

La dimostrazione che m ed f(m) sono primi tra loro è alquanto semplice:

Supponiamo che m abbia un divisore qualsiasi, ossia

$m\equiv 0\,\pmod n$

Si evince immediatamente che

$m^2+m+1\equiv 0^2+0+1\,\pmod n \;\Rightarrow\; m^2+m+1\equiv 1 \,\pmod n\;\forall n>1\,:\,n\in N$

ossia ogni divisore di m non sarà mai un divisore di f(m);
quindi m ed f(m) sono primi tra loro.

Comunque, visti gli altri problemi di aritmetica russa, questo mi sembra fin troppo semplice.
Ho dimenticato qualcosa?

Ciao
Admin

Inviato: gio set 14, 2006 7:00 pm
da Bruno
...

Ciao, Pietro!
Fra un paio di minuti devo chiudere
e quindi mi tocca essere (ahimè)
sbrigativo...
Può essere che abbia frainteso ciò
che hai scritto, e mi scuso subito, ma
non riesco a capire come, dal fatto
che due termini contigui della sequenza
m, f(m), f(f(m)), ... siano coprimi, si
possa concludere che non ci siano
due o più termini nella successione
che abbiano in comune un divisore
non unitario.
Pietro, leggo e vado di fretta... però
sto pensando, per esempio, ai numeri
naturali: due termini contigui sono
sempre coprimi, anche se i membri
della loro bella 'famiglia' non sono
certo tutti primi fra loro.
Che ne dici?
Forse bisogna valutare qualche
altro aspetto di questo problema?

A presto :D

Bruno

Inviato: gio set 14, 2006 10:52 pm
da Tino
Ciao!

Beh, se posso dare un contributo: non credo che la richiesta sia di dimostrare che due qualunque termini della successione sono coprimi, perché per esempio se partiamo da m=1 abbiamo

1, 3, 13, 183,...

3 e 183 evidentemente non sono coprimi...

Ciao ciao

Inviato: ven set 15, 2006 8:04 am
da Admin
Ciao Bruno.

io avevo fatto lo stesso ragionamento di Tino;
ossia ho dimostrato solo che m, f(m), f(f(m)),... sono tutti, nel loro insieme, primi tra loro (non però due qualsiasi di loro; tutti) e che due numeri consecutivi della sequenza sono primi tra loro.

Non è detto che due qualsiasi numeri della sequenza siano coprimi.
Inizialmente stavo cercando un procedimento per dimostrare ciò, ma poi ho notato che, essendo

$m^2+m+1\equiv 0^2+0+1\,\pmod n \;\Rightarrow\; m^2+m+1\equiv 1 \,\pmod n\;\forall n>1\,:\,n\in N$

, il termine consecutivo della sequenza avrà come risultato della congruenza 3, e quindi se m è un multiplo di 3 il secondo termine successivo ad m, nella sequenza sarà anch'esso multiplo di 3.

A questo punto un altro problema potrebbe essere:

"Trovare i valori di m tali che due qualsiasi numeri della sequenza m,f(m),f(f(m)),... siano coprimi."

per $m=3k$ l'ipotesi non è verificata;
continuando a sostituire nella funzione $f(m)=m^2+m+1$ i resti del termine precedente della sequenza si ha:
$f(3)=3^2+1+1=11$
$f(11)=121+1+1=123$
...
...

Ciò ci dice che gli m multipli di 11, multipli di 123, etc. non verificano l'ipotesi.

forse l'ipotesi non è mai verificata?
Idee?

Ciao
Admin

Inviato: ven set 15, 2006 11:01 am
da Bruno
Tino ha scritto:Ciao!

Beh, se posso dare un contributo: non credo che la richiesta sia di dimostrare che due qualunque termini della successione sono coprimi, perché per esempio se partiamo da m=1 abbiamo

1, 3, 13, 183,...

3 e 183 evidentemente non sono coprimi...

Ciao ciao
Ok, Pietro e Tino.

Ovviamente, non ho fatto il calcolo dei primi termini
e quindi non mi sono accorto di questo (vabbè... m
dev'essere maggiore di 1, ma il concetto non cambia).
Comunque, è stato senz'altro opportuno questo chiarimento,
data l'equivocabile formulazione del testo.
Grazie!

Volo...

Un saluto a tutti :D

Bruno