"Aritmetica russa" - 6. Funzioni di funzioni

Forum dedicato ai quesiti irrisolti presenti nella collezione di Base5, nel vecchio forum ed in quello attuale.

Moderatori: Gianfranco, Bruno

Rispondi
Admin
Amministratore del sito
Amministratore del sito
Messaggi: 869
Iscritto il: mer apr 20, 2005 3:47 pm
Località: Benevento

"Aritmetica russa" - 6. Funzioni di funzioni

Messaggio 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
Ultima modifica di Admin il gio mag 17, 2007 9:18 pm, modificato 2 volte in totale.
Pietro Vitelli (Amministratore del Forum)
"Un matematico è una macchina che converte caffè in teoremi" Paul Erdös
www.pvitelli.net

Bruno
Livello 10
Livello 10
Messaggi: 2020
Iscritto il: lun nov 21, 2005 6:07 pm
Località: Bologna

Messaggio 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
(Bruno)

...........................
Invisibile un vento
l'ha apena sfioragia
sospension d'un momento;
e la bola iridessente gera 'ndagia.
{Biagio Marin}
................................................................
Meglio soluzioni sbagliate che risposte esatte.
{Rudi Mathematici}

Tino
Livello 5
Livello 5
Messaggi: 221
Iscritto il: mer mag 25, 2005 9:20 am
Località: Verona

Messaggio 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
"Oh! But I have been blind- blind. Complex, I have said?
Complicated? Mais non. Of a simplicity extreme - extreme.
And miserable one that I am, I saw nothing - nothing."
(Peril At End House)

Admin
Amministratore del sito
Amministratore del sito
Messaggi: 869
Iscritto il: mer apr 20, 2005 3:47 pm
Località: Benevento

Messaggio 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
Pietro Vitelli (Amministratore del Forum)
"Un matematico è una macchina che converte caffè in teoremi" Paul Erdös
www.pvitelli.net

Bruno
Livello 10
Livello 10
Messaggi: 2020
Iscritto il: lun nov 21, 2005 6:07 pm
Località: Bologna

Messaggio 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
(Bruno)

...........................
Invisibile un vento
l'ha apena sfioragia
sospension d'un momento;
e la bola iridessente gera 'ndagia.
{Biagio Marin}
................................................................
Meglio soluzioni sbagliate che risposte esatte.
{Rudi Mathematici}

Rispondi