78. Di problemi strafighi ne abbiamo?

Numeri interi, divisibilità, primalità, ed equazioni a valori interi.

78. Di problemi strafighi ne abbiamo?

Messaggioda Giovanni98 » 15/01/2017, 15:12

Determinare tutte le funzioni $f:\mathbb{Z^{+}} \rightarrow \mathbb{Z^{+}}$ suriettive tali che ogni primo $p$ divide $f(x)+f(y)$ se e solo se divide $f(x+y)$.
Avatar utente
Giovanni98
 
Messaggi: 1255
Iscritto il: 27/11/2014, 14:30

Re: 78. Di problemi strafighi ne abbiamo?

Messaggioda bern1-16-4-13 » 16/01/2017, 23:21

Testo nascosto:
Nel corso della dimostrazione il fatto j verrà spesso abbreviato Fj.

Fatto 1: $f\left(x\right)>1\ \ \forall x>1$.
Dimostrazione: se per assurdo esistesse $x>1$ tale che $f\left(x\right)=1$ allora per l'ipotesi del problema dovremmo avere che $f\left(x-1\right)+f\left(1\right)$ non è divisibile per nessun primo, quindi è uguale a $1$, assurdo perché $f$ va in $\mathbb{Z}^+$.

Fatto 2: per ogni primo $p$ sia $A_p\subseteq\mathbb{Z}^+:\ \ p\mid f\left(x\right)\Leftrightarrow x\in A_p$. Allora, detto $a_p$ il più piccolo elemento di $A_p$ (esiste per la suriettività!), si ha che gli elementi di $A_p$ sono in progressione aritmetica di ragione $a_p$.
Dimostrazione: sfruttando l'ipotesi del problema, con una semplice induzione si riesce a far vedere che $p\mid f\left(ka_p\right)\ \ \forall\ k\in\mathbb{Z}^+$. Adesso supponiamo per assurdo che esistano $h,\ 1\le j<a_p$ tali che $p\mid f\left(ha_p+j\right)$. Ma allora per l'ipotesi del problema, poiché $p\mid f\left(ha_p\right)\wedge\ p\mid f\left(ha_p+j\right)$, si ha che $p\mid f\left(j\right)$ che va contro l'ipotesi che $a_p$ fosse il minimo di $A_p$.
Un corollario di F2 è che $f\left(1\right)=1$, altrimenti se $f\left(1\right)$ fosse divisibile per almeno un primo $q$ allora tutti gli elementi dell'immagine di $f$ lo sarebbero, e addio suriettività.

Fatto 3: per ogni primo $p$ si ha che $a_p$ è primo.
Dimostrazione: ragioniamo come al solito per assurdo, quindi supponiamo esistano due primi distinti $p_1$ e $p_2$ tali che divide $p_2\mid a_{p_1},\ p_2<a_{p_1}$. Allora, poiché $f\left(p_2\right)>1$ per F1, esiste un primo $q$ che divide $f\left(p_2\right)$, quindi $a_q\stackrel{F2}{\mid}p_2\mid a_{p_1}\Rightarrow a_q\mid a_{p_1}$. Per come abbiamo definito $p_1$ e $p_2$ sappiamo inoltre che $a_q\le p_2<a_{p_1}$, quindi $q\ne p_1$. A questo punto se $a_q\mid a_{p_1}$ ciò significa che nell'immagine di $f$ tutti i multipli di $p_1$ saranno anche multipli di $q$, ciao ciao suriettività.
Un corollario di F3 è che $f\left(p\right)$ è una potenza di un primo (non necessariamente uguale a $p$) per ogni $p$ primo.

Fatto 4: per ogni primo $p$ si ha che $a_p=p$.
Dimostrazione: facendo attenzione a non confondere con la notazione della dimostrazione per assurdo di F3, definiamo $p_n$ l'$n$-esimo numero primo in ordine crescente.
Dimostriamo F4 per induzione su $n$. Passo base: $f\left(1\right)+f\left(1\right)=2\Rightarrow 2\mid f\left(2\right)$.
Veniamo al passo induttivo. Supponiamo F4 vero per $p_n$ con $n$ che va da $1$ a $k-1$. Supponiamo per assurdo che $a_{p_k}=p_l$ con $l\ne k$ (grazie all'ipotesi induttiva estesa e grazie al corollario di F3 sicuramente $l>k$). Ma allora se $p_k\mid f\left(p_l\right)$ per l'ipotesi del problema abbiamo che per ogni $0<s<p_k$ si ha che $p_k\mid f\left(s\right)+f\left(p_l-s\right)$. Inoltre $p_k\not\mid f\left(s\right)$ altrimenti contraddiremmo che $a_{p_k}=p_l$. Ma allora sfruttando il fatto che $p_l>p_k$, abbiamo che per un semplice pigeonhole esisteranno $0<s_1<s_2<p_l$ con $s_1\ne p_l-s_2$ tali che $p_k\mid f\left(s_1\right)+f\left(s_2\right)$. Quindi $p_k\mid f\left(s_1+s_2\right)$, ma d'altronde $p_l\ne s_1+s_2<2p_l$, quindi non $s_1+s_2$ non è multiplo di $p_l$, il che va a contraddire il fatto che $a_{p_k}=p_l$.

Fatto 5: per ogni $n\in\mathbb{Z}^+$ l'insieme dei primi che dividono $n$ coincide con l'insieme dei primi che dividono $f\left(n\right)$.
Dimostrazione: conseguenza di F2 e F4.

Fatto 6: $f\left(p^t\right)=p^t$ per ogni $\left(p,t\right)\in\mathbb{P}\times\mathbb{Z}^+$.
Dimostrazione: verrebbe più veloce con Zsigmondy, ma facciamo le brave persone e accontentiamoci di un'induzione + lemma del guadagno di un primo (LGP). Passo base: $t=1$. Poniamo per assurdo $f\left(p\right)=p^{d>1}$. Ma allora $f\left(1\right)+f\left(p\right)=1+p^d$. Ma essendo $d>1$, per LGP esisterà quindi un primo che divide $1+p^d$ ma che non divide $1+p$, quindi per F5 che non divide $f\left(1+p\right)$, assurdo.
Passo induttivo: F6 vero per ogni $t<k$. Allora supponiamo per assurdo che $f\left(p^k\right)=p^{e\ne k}$.
Caso 1: $e<k$. Allora $f\left(p^{e-1}\right)+f\left(p^k\right)=p^{e-1}\left(p+1\right)$ il che significa che quest'ultima quantità ha gli stessi fattori primi di $f\left(p^{e-1}+p^k\right)$, quindi per F5 ha gli stessi fattori primi di $p^{e-1}+p^k=p^{e-1}\left(p^{k+1-e}+1\right)$. Ma allora $p-1$ ha gli stessi fattori primi di $p^{k+1-e}+1$, assurdo per LGP, infatti $k+1-e\ge 2$.
Caso 2: $e>k$. Allora $f\left(p^{k-1}\right)+f\left(p^k\right)=p^{k-1}+p^e=p^{k-1}\left(p^{e+1-k}+1\right)$, quindi quest'ultima quantità ha gli stessi fattori primi di $f\left(p^{k-1}+p^k\right)$, quindi per F5 ha gli stessi fattori primi di $p^{k-1}+p^k=p^{k-1}\left(p-1\right)$. Analogamente al caso 1 quindi $p-1$ ha gli stessi fattori primi di $p^{e+1-k}+1$, assurdo per LGP, infatti $e+1-k\ge 2$.

Fatto 7: $f\left(n\right)=n\ \ \forall n\in\mathbb{Z}^+$.
Dimostrazione: supponiamo per assurdo che per un certo $m$ si abbia $f\left(m\right)=m_1\ne m$. Allora sia $q$ un primo maggiore sia di $m_1$ che di $m$, in modo che quindi $m_1\not\equiv m\pmod{q}$. Sia $g$ un generatore modulo $q$. Sia $q_1$ un primo congruo $g$ modulo $q$ (esiste per Dirichlet). Quindi per un opportuno intero $v$ si avrà $q_1^v\equiv -m_1\pmod{q}$. Ma allora $f\left(m\right)+f\left(q_1^v\right)\stackrel{F6}{=}m_1+q_1^v$ è multiplo di $q$.
D'altronde per F5 $q\mid f\left(m+q^v\right)\Leftrightarrow q\mid m+q^v$, il che non può accadere in quanto $m\not\equiv m_1\pmod{q}$.


Bel problema (anche se immagino ci sarà un modo più veloce di come lo ho fatto io (almeno spero sia giusto)...vero?)! Fonte?
mentre il mondo persiste nei suoi sanguinosi conflitti, la vera guerra è combattuta dai matematici
bern1-16-4-13
 
Messaggi: 179
Iscritto il: 27/11/2014, 22:10
Località: Firenze

Re: 78. Di problemi strafighi ne abbiamo?

Messaggioda Giovanni98 » 17/01/2017, 14:43

Soluzione corretta.

Riguardo la prima domanda la mia soluzione (per esempio) é più corta ed usa il postulato di Bertrand, sfruttando il fatto che $f(p) = p$ dove $p$ é primo quindi direi che ci sono diversi modi più sbrigativi per risolvere il problema. Per quanto riguarda la fonte é un ISL N5 mi sembra del 2007. :)
Avatar utente
Giovanni98
 
Messaggi: 1255
Iscritto il: 27/11/2014, 14:30


Torna a Teoria dei Numeri

Chi c’è in linea

Visitano il forum: Nessuno e 0 ospiti