Ho paura di mettere il livello

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

Ho paura di mettere il livello

Messaggioda Veritasium » 18/08/2016, 22:40

Sia [tex]\psi: \mathbb Z^+ \longrightarrow \mathbb Z^+[/tex] definita come
[tex]\psi(n) = \sum_{k = 1}^{n} (k, n) \ \ \forall n \in \mathbb Z^+[/tex] dove [tex](k, n)[/tex] denota il massimo comun divisore tra $k$ e $n$

a) mostrare che $\psi$ è moltiplicativa, ovvero che $\psi(m)\psi(n) = \psi(mn)$ per ogni coppia $(m, n)$ di interi positivi coprimi.
b) mostrare che per ogni intero positivo $a$ l'equazione $\psi(x) = ax$ ha soluzione in $\mathbb Z^+$
c) determinare tutti gli $a \in \mathbb Z^+$ tale che l'equazione $\psi(x) = ax$ abbia una sola soluzione.
Veritasium
 
Messaggi: 206
Iscritto il: 30/03/2015, 20:36

Re: Ho paura di mettere il livello

Messaggioda Rho33 » 19/08/2016, 0:04

Thumbs up per il titolo, avevo una mezza idea di metterne uno simile :lol: :lol: :mrgreen:
Rho33
 
Messaggi: 489
Iscritto il: 16/09/2014, 11:14

Re: Ho paura di mettere il livello

Messaggioda Rho33 » 21/08/2016, 9:03

Problema originale secondo me :D A proposito, da dove viene? Non mi dispiacerebbe approfondire le funzioni aritmetiche e le loro proprietà! Comunque, sto problema l'ho risolto in circostanze molto strambe: ieri non riuscivo ad addormentarmi ed ho iniziato a pensarci, ho impiegato tipo 1 ora per fare il b),c) perché non trovavo i due modi, questo perché sono uno scemo, quindi spero davvero sia corretta :oops:

Testo nascosto:
Riscriviamo innanzitutto la nostra funzione in una forma più consona, sfruttando sostanzialmente la stessa idea della dimostrazione di:
$$\sum_{d \mid n} \varphi (d)=n$$ ovvero se $(k,n)=l$ per un certo $l$, è ovvio che per come è definito il MCD si ha $ l \mid n$ , $l \mid k$ e $\left ( \dfrac {k}{l}, \dfrac {n}{l} \right )=1$. Ma allora il numero di interi $k$ tali che $(k,n)=l$ è esattamente $\varphi (\frac {n}{l})$. Ora chiamo $l=d$ perché è un divisore e mi piace di più. Vale quindi:

$$\psi (n)= \sum_{k = 1}^{n} (k, n)= \sum_{d \mid n} \varphi \left (\dfrac {n}{d} \right ) \cdot d= \sum_{d \mid n} \varphi (d) \cdot \dfrac {n}{d}= n \cdot \sum_{d \mid n} \dfrac { \varphi (d)}{d}$$ dove nel penultimo passaggio abbiamo usato che se $d$ è divisore, anche $\dfrac {n}{d}$ lo è e quindi la somma è invariata.

Veniamo ora al problema vero e proprio:

a) Siano $m,n$ due interi positivi coprimi e sia $d$ un divisore di $m \cdot n$. Chiaramente $d= s \cdot t$ dove $s \mid m$ e $t \mid n$ e $(s,t)=1$. Ma allora si ha (sfruttando la moltiplicatività della $\varphi$ ):

$$\psi (m \cdot n)= m \cdot n \cdot \sum_{s \cdot t \mid m \cdot n} \dfrac { \varphi (s \cdot t)}{s \cdot t}= m \cdot n \cdot \left ( \sum_{s \mid m} \dfrac {\varphi (s)}{s} \right ) \cdot \left ( \sum_{t \mid n} \dfrac {\varphi (t)}{t} \right )= \psi (m) \cdot \psi (n) $$

b) Per dimostrare che $\psi (x)=x \cdot a$ ha sempre soluzione per qualsiasi $a$, basta far vedere per le potenze di primi, poi grazie al punto a) ed al TFA la tesi segue subito. Calcoliamo innanzitutto:

$$\psi (p^{\alpha})= p^{\alpha} \cdot \sum_{d \mid p^{\alpha}} \dfrac { \varphi (d)}{d}=p^{\alpha} \cdot \left (1+ \alpha \cdot \dfrac {p-1}{p} \right)= (\alpha +1)p^{\alpha}-\alpha \cdot p^{\alpha -1} $$

Ora, se voglio $a$ potenza di un primo con esponente $k$ generico, ecco il trucco, scegliendo $\alpha$ opportunamente:

$$ (\alpha +1)p^{\alpha}-\alpha \cdot p^{\alpha -1}=p^{\alpha +k} \iff (\alpha +1)p- \alpha=p^{k+1} \iff \alpha =\dfrac {p(p^{k}-1)}{p-1}$$ e quindi $\alpha$ è sempre intero in questo modo!

Segue che:

$$\psi (p^{\alpha})=p^{\alpha +k}$$ scegliendo l' $\alpha$ trovato in precedenza, e quindi abbiamo sistemato tutte le generiche potenze di primi $p^k$, quindi per moltiplicatività si finisce.

c) Veniamo ora all'ultimo punto. Sappiamo dal punto b) che tutti gli $a$ si possono rappresentare in almeno un modo. Dimostro che tutti gli $a$ si possono rappresentare in almeno due modi, escludendo $a=1$ che sarà l'unico valore accettabile (ovvio che $a=1$ si rappresenta solo quando $x=1$, poiché $\psi (x)=x$ per $x > 1$ è ovviamente assurdo!).

Ecco il secondo trucco: usare le potenze di due! Si nota abbastanza facilmente (basta fare il conto con la forma nuova) che, posto $\alpha=2k$, si ha:

$$\psi (2^{\alpha})=2^{\alpha} \cdot (1+k)$$ e quindi tutti gli $a>1$ si possono rappresentare anche in questo modo! Non rimane da controllare l'unico caso che è in comune con il punto b), ovvero:

$$\psi (2^2)=2^2 \cdot 2$$ quindi il caso $a=2$! Dobbiamo trovare un numero random che soddisfi $\psi (x)=x \cdot 2$ in modo da avere anche in questo caso due modi diversi. Bene, mi sono appena accorto un tale $x \neq 4$ non esiste, questo perché vorrei un numero coprimo con $x-3$ degli $x-2$ interi tra $1$ ed $x$ e che abbia in comune un solo fattore $2$ con il rimanente, in modo che $$(1,x)=1, (2,x)=1, \dots , (x-k,x)=2, (x-k+1,x)=1, \dots , (x-1,x)=1, (x,x)=x$$ ma ciò è assurdo perché dovrebbe essere pari.

In conclusione gli unici due valori che soddisfano sono $a=1, a=2$.
Rho33
 
Messaggi: 489
Iscritto il: 16/09/2014, 11:14

Re: Ho paura di mettere il livello

Messaggioda Veritasium » 21/08/2016, 11:40

Buoni l'a) e il b) :D
Purtroppo il c) è errato: per ora ti dico solo che l'errore non è nei passaggi algebrici né nella struttura dimostrativa, ma è concettuale, quasi una dimenticanza, e si basa sul fatto che appunto [tex]a = 2[/tex] non ha una seconda rappresentazione
Veritasium
 
Messaggi: 206
Iscritto il: 30/03/2015, 20:36

Re: Ho paura di mettere il livello

Messaggioda Rho33 » 21/08/2016, 12:00

Oh madonna, che scemo! :oops: In questo modo tutti gli $a$ potenze di due non li sto rappresentando una seconda volta! (è questo l'errore vero? mi sembra che tutti i dispari ed i pari non potenze di due invece li rappresento e vadano bene...). Appena posso cerco di sistemare il buco, grazie mille per avermelo fatto notare! :oops:
Rho33
 
Messaggi: 489
Iscritto il: 16/09/2014, 11:14

Re: Ho paura di mettere il livello

Messaggioda Veritasium » 21/08/2016, 12:04

Figurati, sì è quello :)
Veritasium
 
Messaggi: 206
Iscritto il: 30/03/2015, 20:36

Re: Ho paura di mettere il livello

Messaggioda Rho33 » 21/08/2016, 16:50

Allora, non garantisco nulla, ma spero di averla completata e riparata! :oops:

Testo nascosto:
Dimostro che tutti ed i soli $a$ che soddisfano sono le potenze di $2$ (casi $a=1,a=2$ già fatti come esempio), in particolare abbiamo già visto come poter rappresentare in due modi diversi tutti gli altri interi positivi. In particolare dimostro:

$$a=\dfrac {\psi (n)}{n}= \sum_{d \mid n} \dfrac {\varphi (d)}{d}= 2^{\alpha} \Longrightarrow n=2^{\beta}$$ chiaramente questo dimostra che posso ottenere un $a$ potenza di $2$ solo se anche $n$ lo è.

Osservazione importante: $\varphi (x) \equiv 0 \pmod 2 \iff x >2$. $\Box$

Manipoliamo la sommatoria facendo il m.c.m. ed otteniamo ($d_1=1,d_k=n$):

$$a= \sum_{d \mid n} \dfrac {\varphi (d)}{d}= \dfrac {\dfrac {n}{d_1} \cdot \varphi (d_1)+ \dfrac {n}{d_2} \cdot \varphi (d_2)+ \dots +\dfrac {n}{d_k} \cdot \varphi (d_k) }{n}= \dfrac {n + \dfrac {n}{d_2} \cdot \varphi (d_2)+ \dots + \varphi (n)}{n}$$

Supponiamo per assurdo che $n$ non sia una potenza di $2$ e distinguiamo in tre casi:

$\bullet \ \ v_2(n)=0$. Si avrà $n= p_1 ^{\beta_1} \cdot \dots \cdot p_h^{\beta_h}$. Ma allora sia numeratore che denominatore sono dispari, quindi $a$ non può essere una potenza di $2$, assurdo!.

$\bullet \ \ v_2(n) = 1$. WLOG $d_2=2$ ed $n= 2 \cdot p_1 ^{\beta_1} \cdot \dots \cdot p_h^{\beta_h}$ . Ciò è assurdo, perché il numeratore della frazione sarà dispari ed il denominatore sarà pari, ma $a$ era una potenza di due, mentre la frazione non è nemmeno intera!

$\bullet \ \ v_2(n)=c >1$. Si avrà: $n= 2^c \cdot p_1 ^{\beta_1} \cdot \dots \cdot p_h^{\beta_h}$. Al numeratore tutti sono pari, ora raccogliamo la massima potenza di $2$ possibile (essa è chiaramente $2^{c-1}$ perché $2$ è un divisore e $\varphi (2)=1$). Ora il numeratore è dispari, mentre il denominatore ha ancora un fattore $2$, assurdo!

Allora $n$ è una potenza di $2$ e quindi fine (?).
Rho33
 
Messaggi: 489
Iscritto il: 16/09/2014, 11:14

Re: Ho paura di mettere il livello

Messaggioda Veritasium » 21/08/2016, 17:16

Ok, direi che ci siamo :D
Solo per precisare, mostrare che se [tex]a[/tex] è una potenza di [tex]2[/tex] lo è anche [tex]x[/tex] conclude perché se [tex]a[/tex] si potesse rappresentare in due modi, si avrebbe [tex]\frac{\psi(2^\alpha)}{2^\alpha} = \frac{\psi(2^\beta)}{2^\beta}[/tex] ([tex]\alpha \neq \beta[/tex]) che dalla formula della [tex]\psi(p^k)[/tex] porta a [tex]\frac{\alpha + 2}{2} = \frac{\beta + 2}{2},[/tex] assurdo!
Veritasium
 
Messaggi: 206
Iscritto il: 30/03/2015, 20:36

Re: Ho paura di mettere il livello

Messaggioda Rho33 » 21/08/2016, 17:24

Ottimo, finalmente questo bel problema è risolto! Ora non puoi esimerti dal dirmi la fonte/livello :lol: :mrgreen:
Rho33
 
Messaggi: 489
Iscritto il: 16/09/2014, 11:14

Re: Ho paura di mettere il livello

Messaggioda Veritasium » 21/08/2016, 17:27

Rho33 ha scritto:Ottimo, finalmente questo bel problema è risolto! Ora non puoi esimerti dal dirmi la fonte/livello :lol: :mrgreen:

Certo, la fonte è ISL2004 N2. Come livello, a mio parere rientra perfettamente nei canoni del L05, anche perché ha 3 punti
Veritasium
 
Messaggi: 206
Iscritto il: 30/03/2015, 20:36


Torna a Teoria dei Numeri

Chi c’è in linea

Visitano il forum: Nessuno e 1 ospite