Staffetta tdn

Numeri interi, razionali, divisibilità, equazioni diofantee, ...
Avatar utente
kn
Messaggi: 508
Iscritto il: 23 lug 2007, 22:28
Località: Sestri Levante (Genova)
Contatta:

Messaggio da kn » 30 giu 2009, 16:47

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...
Ultima modifica di kn il 30 giu 2009, 17:41, modificato 1 volta in totale.
Viviamo intorno a un mare come rane intorno a uno stagno. (Socrate)

Avatar utente
jordan
Messaggi: 3988
Iscritto il: 02 feb 2007, 21:19
Località: Pescara
Contatta:

Messaggio da jordan » 30 giu 2009, 17:13

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:
The only goal of science is the honor of the human spirit.

Avatar utente
julio14
Messaggi: 1208
Iscritto il: 11 dic 2006, 18:52
Località: Berlino

Messaggio da julio14 » 30 giu 2009, 17:26

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?

Avatar utente
jordan
Messaggi: 3988
Iscritto il: 02 feb 2007, 21:19
Località: Pescara
Contatta:

Messaggio da jordan » 30 giu 2009, 17:36

Hai ragione, ma tanto non è utilizzato e il lemma così enunciato è anche corretto :wink:
The only goal of science is the honor of the human spirit.

Avatar utente
kn
Messaggi: 508
Iscritto il: 23 lug 2007, 22:28
Località: Sestri Levante (Genova)
Contatta:

Messaggio da kn » 30 giu 2009, 17:45

@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?
Viviamo intorno a un mare come rane intorno a uno stagno. (Socrate)

Avatar utente
kn
Messaggi: 508
Iscritto il: 23 lug 2007, 22:28
Località: Sestri Levante (Genova)
Contatta:

Messaggio da kn » 30 giu 2009, 18:10

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))
Viviamo intorno a un mare come rane intorno a uno stagno. (Socrate)

fph
Site Admin
Messaggi: 3763
Iscritto il: 01 gen 1970, 01:00
Località: in giro
Contatta:

Messaggio da fph » 30 giu 2009, 19:51

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? ;)
--federico
[tex]\frac1{\sqrt2}\bigl(\left|\text{loves me}\right\rangle+\left|\text{loves me not}\right\rangle\bigr)[/tex]

Tibor Gallai
Messaggi: 1776
Iscritto il: 17 nov 2007, 19:12

Messaggio da Tibor Gallai » 30 giu 2009, 20:03

Ma non era sempre lo stesso Jordan?? Oh wait... :shock:
[quote="Pigkappa"]Penso che faresti un favore al mondo se aprissi un bel topic di bestemmie da qualche parte in modo che ti bannino subito.[/quote]

spugna
Messaggi: 421
Iscritto il: 19 mar 2009, 22:18
Località: Forlì

Messaggio da spugna » 30 giu 2009, 20:04

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.
"Bene, ora dobbiamo massimizzare [tex]\dfrac{x}{(x+100)^2}[/tex]: come possiamo farlo senza le derivate? Beh insomma, in zero fa zero... a $+\infty$ tende a zero... e il massimo? Potrebbe essere, che so, in $10^{24}$? Chiaramente no... E in $10^{-3}$? Nemmeno... Insomma, nella frazione c'è solo il numero $100$, quindi dove volete che sia il massimo se non in $x=100$..?" (da leggere con risatine perfide e irrisorie in corrispondenza dei puntini di sospensione)

Maledetti fisici! (cit.)

Avatar utente
kn
Messaggi: 508
Iscritto il: 23 lug 2007, 22:28
Località: Sestri Levante (Genova)
Contatta:

Messaggio da kn » 30 giu 2009, 22:46

Bravo! Tutto perfetto! 8)
Vai con il 21! :D
Viviamo intorno a un mare come rane intorno a uno stagno. (Socrate)

spugna
Messaggi: 421
Iscritto il: 19 mar 2009, 22:18
Località: Forlì

Messaggio da spugna » 01 lug 2009, 07:10

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 $
"Bene, ora dobbiamo massimizzare [tex]\dfrac{x}{(x+100)^2}[/tex]: come possiamo farlo senza le derivate? Beh insomma, in zero fa zero... a $+\infty$ tende a zero... e il massimo? Potrebbe essere, che so, in $10^{24}$? Chiaramente no... E in $10^{-3}$? Nemmeno... Insomma, nella frazione c'è solo il numero $100$, quindi dove volete che sia il massimo se non in $x=100$..?" (da leggere con risatine perfide e irrisorie in corrispondenza dei puntini di sospensione)

Maledetti fisici! (cit.)

GioacchinoA
Messaggi: 137
Iscritto il: 13 feb 2009, 15:44
Località: Bari

Messaggio da GioacchinoA » 01 lug 2009, 10:46

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?
Ultima modifica di GioacchinoA il 01 lug 2009, 14:59, modificato 1 volta in totale.

Avatar utente
jordan
Messaggi: 3988
Iscritto il: 02 feb 2007, 21:19
Località: Pescara
Contatta:

Messaggio da jordan » 01 lug 2009, 13:31

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:
The only goal of science is the honor of the human spirit.

Natalino
Messaggi: 30
Iscritto il: 30 apr 2008, 23:37

Messaggio da Natalino » 01 lug 2009, 14:47

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} $?

GioacchinoA
Messaggi: 137
Iscritto il: 13 feb 2009, 15:44
Località: Bari

Messaggio da GioacchinoA » 01 lug 2009, 15:09

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 $

Rispondi