Pagina 5 di 33

Inviato: 30 giu 2009, 16:47
da kn
jordan ha scritto:Problema 19.
Siano fissati degli interi positivi $ a,b,c $. Mostrare che esiste un intero positivo $ x $ tale che $ a^x+x \equiv b \pmod c $.
Soluzione problema 19.

Lemma - $ \displaystyle~\forall n, m\in\mathbb{N}:m>0 $ la successione $ \displaystyle~\{n^i\}_{i>0} $ è periodica $ \displaystyle~\pmod m $ e il periodo divide $ \displaystyle~\phi\left(\frac{m}{(m,n)}\right) $.
Poniamo $ \displaystyle~v=\frac{m}{(m,n)} $. Chiaramente $ \displaystyle~n^{\phi(v)}\equiv1\pmod v $ (dato che $ \displaystyle~(n,v)=1 $). Abbiamo quindi $ \displaystyle~v\mid n^{\phi(v)}-1 $, da cui $ \displaystyle~m\mid (m,n)(n^{\phi(v)}-1) $ e a maggior ragione $ \displaystyle~m\mid n^x(n^{\phi(v)}-1)=n^{x+\phi(v)}-n^x,~\forall x>0 $. Ora con una somma telescopica (se non vi piace c'è anche l'induzione) si dimostra che $ \displaystyle~\forall x>0,0<x'\le\phi(v)~x\equiv x'\pmod{\phi(v)}\Rightarrow n^x\equiv n^{x'}\pmod m $, da cui la tesi.

Corollario - $ \displaystyle~\forall n, m\in\mathbb{N}:m>0 $ la successione $ \displaystyle~\{n^i\}_{i>0} $ è periodica $ \displaystyle~\pmod m $ e il periodo divide $ \displaystyle~\phi(m) $.

Ora ragioniamo per induzione estesa su c:
"Passo base" ( :lol: ): Per $ \displaystyle~c=1 $ la tesi è ovvia. (In realtà per l'induzione questo caso è inutile)
Passo induttivo: Vogliamo che esista un x che soddisfa $ \displaystyle~a^x+x\equiv b\pmod c $, oppure, ponendo $ \displaystyle~x=k\phi(c)+j,~0<j\le\phi(c) $, che $ \displaystyle~a^{k\phi(c)+j}+k\phi(c)+j\equiv b\pmod c $, cioè (per il lemma) $ \displaystyle~a^j+j\equiv -k\phi(c)+b\pmod c $.
Ora poniamo $ \displaystyle~m=(\phi(c),c) $ (da cui abbiamo che $ \displaystyle~m\le\phi(c)<c $) e $ \displaystyle~\phi(c)=rm $ (quindi $ \displaystyle~\left(r,\frac{c}{m}\right)=1 $). Rimane da dimostrare che per qualche $ \displaystyle~(k,j) $ si ha $ \displaystyle~a^j+j\equiv -krm+b\pmod c $.
Caso $ \displaystyle~m>1 $: Per l'ipotesi induttiva abbiamo che $ \displaystyle~\exists j:a^j+j\equiv b\pmod m $ e possiamo supporre $ \displaystyle~0<j\le\phi(c) $ (che non lede la generalità della tesi dato che $ \displaystyle~m\mid\phi(c)\wedge\phi(m)\mid\phi(c) $). Per qualche s abbiamo cioè $ \displaystyle~a^j+j=ms+b $. Rimane da provare che per qualche k $ \displaystyle~ms+b\equiv -krm+b\pmod c $, ovvero $ \displaystyle~mkr\equiv -ms\pmod c $. Questa ultima equivalenza si riduce a $ \displaystyle~kr\equiv -s\pmod{\frac{c}{m}} $. Dato che $ \displaystyle~\left(r,\frac{c}{m}\right)=1 $, possiamo ricavare direttamente k: $ \displaystyle~k\equiv -sr^{-1}\pmod{\frac{c}{m}} $. L'esistenza di k è dimostrata dato che gli ultimi passaggi sono invertibili.
Caso $ \displaystyle~m=1 $: Per un j a scelta si ricava direttamente k: $ \displaystyle~k\equiv(a^j+j-b)r^{-1} $.
Di conseguenza esiste anche un x che rispetta la tesi. Fatemi sapere...

Inviato: 30 giu 2009, 17:13
da jordan
kn ha scritto:[...] Vogliamo che esista un x che soddisfa $ \displaystyle~a^x-x\equiv b\pmod c $[...]
Correggi qualche segno, per il resto complimenti per la chiarezza :wink:

Inviato: 30 giu 2009, 17:26
da julio14
kn ha scritto:$ \displaystyle~\forall x>0,0<x'\le\phi(v)~n^x\equiv n^{x'}\pmod m\Leftrightarrow x\equiv x'\pmod{\phi(v)} $
mmm qua mi è chiara la freccia verso sinistra, ma non quella verso destra... anche perché dimostrerebbe che il periodo è la phi, e non semplicemente la divide. O mi sbaglio?

Inviato: 30 giu 2009, 17:36
da jordan
Hai ragione, ma tanto non è utilizzato e il lemma così enunciato è anche corretto :wink:

Inviato: 30 giu 2009, 17:45
da kn
@julio14: corretto :wink:
jordan ha scritto:Correggi qualche segno, per il resto complimenti per la chiarezza :wink:
Sì scusa avevo letto male :lol:
Mi dai il via libera per il problema 20?

Inviato: 30 giu 2009, 18:10
da kn
Problema 20. (da un lemma di jordan...)
Dimostrare che se per quattro interi positivi (non necessariamente distinti) $ \displaystyle~w,x,y,z $ vale $ \displaystyle~wx=yz $ allora esistono quattro interi positivi $ \displaystyle~a,b,c,d $ tali che
$ \displaystyle~\begin{cases}w=ab\\ x=cd\\ y=ac\\ z=bd\end{cases} $

(Veramente facile... jordan in una dimostrazione l'ha addirittura dato per scontato :o così ne ho approfittato 8))

Inviato: 30 giu 2009, 19:51
da fph
kn ha scritto:Problema 20. (da un lemma di jordan...)
Quello delle curve chiuse nel piano, quello della forma canonica, quello che schiacciava dalla linea del tiro libero, o quello che bazzica il forum? ;)

Inviato: 30 giu 2009, 20:03
da Tibor Gallai
Ma non era sempre lo stesso Jordan?? Oh wait... :shock:

Inviato: 30 giu 2009, 20:04
da spugna
Sperando che funzioni..... :roll: ..........

Essendo $ wx $ e $ yz $ uguali,la loro scomposizione in fattori primi è identica. Sia $ S $ l'insieme di tutti i numeri primi che compaiono in questa scomposizione,includendo eventualmente più volte quelli ripetuti (esempio:$ 48=3 \cdot 2^4 \rightarrow $il $ 2 $ compare $ 4 $ volte in $ S $). Siano $ W,X,Y,Z $ quattro sottoinsiemi di $ S $ contenenti ciascuno i numeri primi che,moltiplicati tra loro,danno come risultato (rispettivamente) i numeri $ w,x,y,z $. In particolare si avrà $ W=\overline{X} \wedge Y=\overline{Z} $. Siano $ A,B,C,D $ altri quattro sottoinsiemi di $ S $ tali che $ A=W \cap Y \wedge B=W \cap Z \wedge C=X \cap Y \wedge D=X \cap Z $. Ricordando che $ W=\overline{X} \wedge Y=\overline{Z} $,si deduce che $ A,B,C,D $ sono a due a due disgiunti. Inoltre:
$ \displaystyle~\begin{cases}A \cup B=(W \cap Y) \cup (W \cap Z)=W\\ C \cup D=(X \cap Y) \cup (X \cap Z)=X\\ A \cup C=(W \cap Y) \cup (X \cap Y)=Y\\ B \cup D=(W \cap Z) \cup (X \cap Z)=Z\end{cases} $
Dunque $ a,b,c,d $ non sono altro che il prodotto degli elementi dei rispettivi insiemi.

P.S.:se uno degli insiemi $ A,B,C,D $ risultasse vuoto,basterebbe prendere $ 1 $ come prodotto dei suoi elementi.

Inviato: 30 giu 2009, 22:46
da kn
Bravo! Tutto perfetto! 8)
Vai con il 21! :D

Inviato: 01 lug 2009, 07:10
da spugna
kn ha scritto:Vai con il 21! :D
Eccolo:

Trovare tutte le soluzioni dell'equazione $ 3^x+7=2^y $ con $ (x,y) \in \mathbb{N}^2 $

Inviato: 01 lug 2009, 10:46
da GioacchinoA
Esamino dapprima i casi in cui una delle due variabili è 0. $ x=0 $ produce la coppia $ (x=0,y=3) $. Il caso $ y=0 $ non produce alcuna coppia. Analizzo modulo 7 e ottengo$ 3^x \equiv 2^y \pmod{7} $ vera quando $ x $ è pari.
Modulo 3 invece $ 2^y \equiv 1 \pmod{3} $, vera quando $ y $ è pari.
Dunque sostituisco $ x=2x' $ e $ y=2y' $ e fattorizzando nella prima ottengo: $ (2^{y'}+3^{x'})(2^{y'}-3^{x'})=7 $. Siccome $ 2^{y'}+3^{x'} > 1 $ posso concludere che: $ 2^{y'}+3^{x'}=7 \wedge 2^{y'}-3^{x'}=1 $. Sommando le due ottengo $ 2^{y'+1}=2^3 \Rightarrow y' = 2 $. Essendo $ y'=2 $ sarà $ x'=1 $ da cui la soluzione $ (x=2,y=4) $.
Pertanto le uniche due soluzioni sono $ (x=0,y=3) \wedge (x=2,y=4) $
Giusto?

Inviato: 01 lug 2009, 13:31
da jordan
GioacchinoA ha scritto:[...] Analizzo modulo 7 e ottengo$ 3^x \equiv 2^y \pmod(7) $ vera quando x è pari.
Modulo 3 invece $ 2^y \equiv 1 \pmod(3) $, vera quando $ y $ è pari.[...]
Si, giusto, comunque quando usi i moduli cerca di usare le parentesi graffe invece delle tonde (e.g. \pmod{7}..)
@spugna, aspettiamo il tuo quesito nella staffetta di algebra.. :roll:

Inviato: 01 lug 2009, 14:47
da Natalino
Scusate ma i simboli $ \cap $ e $ \wedge $ sono equivalenti? Perché vengono usati entrambi nella dimostrazione di spugna.. E la barra sopra alla lettera indica l'insieme complementare vero?

Ma visto che $ W\cup X = S $ non dovrebbe essere $ W=\overline{X} $?

Inviato: 01 lug 2009, 15:09
da GioacchinoA
jordan ha scritto: comunque quando usi i moduli cerca di usare le parentesi graffe invece delle tonde (e.g. \pmod{7})
Ok grazie corretto.

$ \textbf {Problema 22} $
Per ogni $ k $ intero positivo , trovare il più piccolo $ n $ tale che $ 2^k | 5^n -1 $