Grazie mille, bella soluzione
Staffetta tdn
Mi sono ricordato di lui: Problema 5
Trovare tutte le terne (a,b,c),naturali, tali che $ 2^a+2^b+1 \equiv 0 \pmod{2^c-1} $.
Trovare tutte le terne (a,b,c),naturali, tali che $ 2^a+2^b+1 \equiv 0 \pmod{2^c-1} $.
Lo stolto è colui che dice quello che sa.Il saggio è colui che sa quello che dice.
"And then one day you find,ten years have got behind you,no one told when to run,you missed the starting gun"
"And then one day you find,ten years have got behind you,no one told when to run,you missed the starting gun"
Problema 5. Trovare tutti gli $ (a,b,c) \in \mathbb{N}^3 $ t.c. $ 2^c-1|2^a+2^b+1 $.
1. $ c=1 $ dà le terne $ (a,b,1) $.
2. $ c=2 \implies a \equiv b \equiv 0 \pmod 2 $ dà la terne $ (2a,2b,2) $. D'ora in poi wlog $ c>2 $ e $ a \le b $.
3. $ a=0 \implies 2^c-1|2^{b-1}+1 $. Sia $ d $ l'intero tale che $ 0\le d <c $ e $ c|b-1-d $ allora $ 2^c-1|2^d+1 \implies 2^{d-1}(2^{c-d}-1) \le 1 $, ma $ c>2 $,assurdo.
4. Se $ a=b $, sia $ e $ l'intero tale che $ 0\le e <c $ e $ c|a+1-e $, allora $ 2^c-1|2^a+2^b+1 \leftrightarrow 2^c-1|2^e+1 \implies 2^e+1 \ge 2^c-1 \implies 2^{e-1}(2^{c-e}-1) \le 1 $, ma $ c>2 $, assurdo.
5. Siano $ f,g $ due interi tali che $ gcd(a-f,b-g) \ge c $ e $ 0 \le f,g < c $ allora $ 2^c-1|2^a+2^b+1 \leftrightarrow 2^c-1|2^g+2^f+1 $, con $ 0 \le f < g < c $. Ma $ 2^g+1 > 2^{f-1}+2^{g-1}+1 \ge 2^{c-1} \implies 1>2^{c-1}-2^g \implies g=c-1 $. Allora $ 2^f+2^g+1|2^{g+1} \implies (f,g)=(1,2) $.
Concludiamo quindi che tutte e sole le terne sono date da $ (a,b,1),(2a,2b,2),(3a+1,3a+2,3),(3a+2,3a+1,3) $.
1. $ c=1 $ dà le terne $ (a,b,1) $.
2. $ c=2 \implies a \equiv b \equiv 0 \pmod 2 $ dà la terne $ (2a,2b,2) $. D'ora in poi wlog $ c>2 $ e $ a \le b $.
3. $ a=0 \implies 2^c-1|2^{b-1}+1 $. Sia $ d $ l'intero tale che $ 0\le d <c $ e $ c|b-1-d $ allora $ 2^c-1|2^d+1 \implies 2^{d-1}(2^{c-d}-1) \le 1 $, ma $ c>2 $,assurdo.
4. Se $ a=b $, sia $ e $ l'intero tale che $ 0\le e <c $ e $ c|a+1-e $, allora $ 2^c-1|2^a+2^b+1 \leftrightarrow 2^c-1|2^e+1 \implies 2^e+1 \ge 2^c-1 \implies 2^{e-1}(2^{c-e}-1) \le 1 $, ma $ c>2 $, assurdo.
5. Siano $ f,g $ due interi tali che $ gcd(a-f,b-g) \ge c $ e $ 0 \le f,g < c $ allora $ 2^c-1|2^a+2^b+1 \leftrightarrow 2^c-1|2^g+2^f+1 $, con $ 0 \le f < g < c $. Ma $ 2^g+1 > 2^{f-1}+2^{g-1}+1 \ge 2^{c-1} \implies 1>2^{c-1}-2^g \implies g=c-1 $. Allora $ 2^f+2^g+1|2^{g+1} \implies (f,g)=(1,2) $.
Concludiamo quindi che tutte e sole le terne sono date da $ (a,b,1),(2a,2b,2),(3a+1,3a+2,3),(3a+2,3a+1,3) $.
The only goal of science is the honor of the human spirit.
Formulazione equivalente: trovare quanti sono i residui quadratici $ x $ modulo $ p>2 $ tali che esistono interi $ 0 \le a \le b <p $ con $ ab\not \equiv 0 \pmod p $ e $ x+kp=a^2+b^2 $.
Inoltre ogni intero $ q $ tale che dà resto 1 modulo 4 è esprimibile come somma di quadrati. Per cui è sufficiente imporre $ 4|x+kp-1 $. Ma per $ k\in \{1,2,3,4\} $ otteniamo che $ \{p,2p,3p,4p\} $ è bigettiva in $ \{0,1,2,3\} $ da cui la tesi, tutti i $ \frac{p-1}{2} $ residui quadratici.
nb. se vogliamo considerare anche lo zero, l'equazione $ p|a^2+b^2 $, con $ p\nmid ab $ ha soluzione se e solo se $ 4|p-1 $.
Aspetto notizie da tbpl..
Inoltre ogni intero $ q $ tale che dà resto 1 modulo 4 è esprimibile come somma di quadrati. Per cui è sufficiente imporre $ 4|x+kp-1 $. Ma per $ k\in \{1,2,3,4\} $ otteniamo che $ \{p,2p,3p,4p\} $ è bigettiva in $ \{0,1,2,3\} $ da cui la tesi, tutti i $ \frac{p-1}{2} $ residui quadratici.
nb. se vogliamo considerare anche lo zero, l'equazione $ p|a^2+b^2 $, con $ p\nmid ab $ ha soluzione se e solo se $ 4|p-1 $.
Aspetto notizie da tbpl..
The only goal of science is the honor of the human spirit.
dopo conferme da tbpl..
Problema 8
Mostrare che se $ m $ non ha radici primitive allora $ a^{\frac{\phi(m)}{2}} \equiv 1 \pmod m $, per ogni a coprimo con m.
edit: Si definisce radice primitiva (o generatore modulo m) un numero a tale che $ a^{\phi(m)} \equiv 1 \pmod m $, e che $ a^d \not \equiv 1 \pmod m $, per ogni $ d|\phi(m), d<\phi(m) $.
Problema 8
Mostrare che se $ m $ non ha radici primitive allora $ a^{\frac{\phi(m)}{2}} \equiv 1 \pmod m $, per ogni a coprimo con m.
edit: Si definisce radice primitiva (o generatore modulo m) un numero a tale che $ a^{\phi(m)} \equiv 1 \pmod m $, e che $ a^d \not \equiv 1 \pmod m $, per ogni $ d|\phi(m), d<\phi(m) $.
The only goal of science is the honor of the human spirit.
Ok, è passata piu di una settimana, si vede che non è piaciuto molto..
Intanto posto la soluzione e metto un nuovo problema..
Fatto1.Gli interi della forma $ 2,4,p^{\alpha},p^{2\alpha} $ con $ p $ primo >2 hanno almeno una radice primitiva (sta anche sul Gobbino, nel caso non ci crediate provate a dimostrarlo..)
Fatto2.Se n è una potenza di 2 maggiore di 4, allora per induzione 8|a^2-1, e posto che, se a dispari, $ 2^k|a^{2^{k-2}}-1 $ allora $ a^{2^{k-2}} $ è della forma $ 1+b2^k $, allora $ a^{2^{k-1}}=(1+b2^k)^2 \equiv 1 \pmod{2^{k+1}} $.
Fatto 3. Altrimenti esistono due interi x e y coprimi maggiori di 2, tali che il loro prodotto sia n, l'intero che non ha radici primitive. Naturalmente $ \varphi(x)\equiv \varphi(y) \equiv 0 \pmod 2 $. Per cui per la molticatività della phi abbiamo $ a^{\phi(n)/2} \equiv (a^{\phi(x)})^{\phi(y)/2} \equiv 1^{\phi(y)/2} \equiv 1 \pmod{x} $, e analogamente per $ y $, da cui la tesi.
Problema 9. Mostrare che, per ogni x reale, vale $ \displaystyle \sum_{i=0}^{\infty}{[\frac{x+2^i}{2^{i+1}}]}=[x] $, dove [y] denota il piu grande intero che non è maggiore di y.
Intanto posto la soluzione e metto un nuovo problema..
Fatto1.Gli interi della forma $ 2,4,p^{\alpha},p^{2\alpha} $ con $ p $ primo >2 hanno almeno una radice primitiva (sta anche sul Gobbino, nel caso non ci crediate provate a dimostrarlo..)
Fatto2.Se n è una potenza di 2 maggiore di 4, allora per induzione 8|a^2-1, e posto che, se a dispari, $ 2^k|a^{2^{k-2}}-1 $ allora $ a^{2^{k-2}} $ è della forma $ 1+b2^k $, allora $ a^{2^{k-1}}=(1+b2^k)^2 \equiv 1 \pmod{2^{k+1}} $.
Fatto 3. Altrimenti esistono due interi x e y coprimi maggiori di 2, tali che il loro prodotto sia n, l'intero che non ha radici primitive. Naturalmente $ \varphi(x)\equiv \varphi(y) \equiv 0 \pmod 2 $. Per cui per la molticatività della phi abbiamo $ a^{\phi(n)/2} \equiv (a^{\phi(x)})^{\phi(y)/2} \equiv 1^{\phi(y)/2} \equiv 1 \pmod{x} $, e analogamente per $ y $, da cui la tesi.
Problema 9. Mostrare che, per ogni x reale, vale $ \displaystyle \sum_{i=0}^{\infty}{[\frac{x+2^i}{2^{i+1}}]}=[x] $, dove [y] denota il piu grande intero che non è maggiore di y.
The only goal of science is the honor of the human spirit.
Soluzione problema 9. $ \displaystyle \sum_{i=0}^{+\infty}{[\frac{x}{2^{i+1}}+\frac{1}{2}]} $ $ \displaystyle =\sum_{i=0}^{+\infty}{[\frac{x}{2^i}]-[\frac{x}{2^{i+1}}]}=[x] $.
Problema 10. Trovare una formula esplicita per $ \displaystyle \sum_{i=1}^{p-1}[\frac{iq}{p}] $ dove p e q sono coprimi.
Problema 10. Trovare una formula esplicita per $ \displaystyle \sum_{i=1}^{p-1}[\frac{iq}{p}] $ dove p e q sono coprimi.
The only goal of science is the honor of the human spirit.
-
federiko97
- Messaggi: 44
- Iscritto il: 03 nov 2008, 20:36
- Località: Roma
Ke figata 'sta staffetta!!!
Comunque, disegnando un rettangolo con i vertici in (0;0), (p;0), (p;q) e (0;q) abbiamo che $ [\frac{iq}{p}] $ è il numero di punti a coordinate intere dell'i-esima colonna compresi tra la base del rettangolo (esclusa) e la diagonale (ma sulla diagonale non ce ne sono perché (p,q)=1). Quindi la somma prende tutti i punti a coordinate intere strettamento dentro il rettangolo sotto la diagonale, cioè la metà del totale, da cui $ \sum =\frac{(p-1)(q-1)}{2} $
Problema 11
Siano $ v_1,\dots v_n $ dei vettori di lunghezza k a coefficienti interi. Sia p un primo. Dimostrare che se $ n>(p-1)k $ allora esiste un insieme non vuoto $ I\subseteq \{ 1,\dots ,n\} $ tale che:
$ \displaystyle\sum_{i\in I} v_i \equiv (0,\dots ,0) \pmod p $
vale a dire ciascun coefficiente del vettore somma è un multiplo di p.
Comunque, disegnando un rettangolo con i vertici in (0;0), (p;0), (p;q) e (0;q) abbiamo che $ [\frac{iq}{p}] $ è il numero di punti a coordinate intere dell'i-esima colonna compresi tra la base del rettangolo (esclusa) e la diagonale (ma sulla diagonale non ce ne sono perché (p,q)=1). Quindi la somma prende tutti i punti a coordinate intere strettamento dentro il rettangolo sotto la diagonale, cioè la metà del totale, da cui $ \sum =\frac{(p-1)(q-1)}{2} $
Problema 11
Siano $ v_1,\dots v_n $ dei vettori di lunghezza k a coefficienti interi. Sia p un primo. Dimostrare che se $ n>(p-1)k $ allora esiste un insieme non vuoto $ I\subseteq \{ 1,\dots ,n\} $ tale che:
$ \displaystyle\sum_{i\in I} v_i \equiv (0,\dots ,0) \pmod p $
vale a dire ciascun coefficiente del vettore somma è un multiplo di p.
-
federiko97
- Messaggi: 44
- Iscritto il: 03 nov 2008, 20:36
- Località: Roma
Hint pesante: se un sistema di equazioni modulo p ha più variabili di quanto sia la somma dei gradi delle singole equazioni, allora il numero di soluzioni è un multiplo di p
Io credo che alcune entità superiori, pur non avendo odore, possano esistere. Esse influenzano le nostre vite in maniera che nessuno scienziato può comprendere.
-
federiko97
- Messaggi: 44
- Iscritto il: 03 nov 2008, 20:36
- Località: Roma
The show must go on!
Visto che nessuno risponde, ecco un altro problema:
Sia m un intero positivo. Sia $ (x_0, y_0) $ la più piccola soluzione all'equazione $ x^2-3y^2=m $ negli interi positivi.
Si trovi trovi un upper bound di $ x_0 $ (in funzione di $ m $ naturalmente).
Sia m un intero positivo. Sia $ (x_0, y_0) $ la più piccola soluzione all'equazione $ x^2-3y^2=m $ negli interi positivi.
Si trovi trovi un upper bound di $ x_0 $ (in funzione di $ m $ naturalmente).
Io credo che alcune entità superiori, pur non avendo odore, possano esistere. Esse influenzano le nostre vite in maniera che nessuno scienziato può comprendere.
-
exodd
- Messaggi: 728
- Iscritto il: 09 mar 2007, 19:46
- Località: sulle pendici della provincia più alta d'europa
Re: The show must go on!
cioè tale che m sia minimo?federiko97 ha scritto: Sia m un intero positivo. Sia $ (x_0, y_0) $ la più piccola soluzione all'equazione $ x^2-3y^2=m $ negli interi positivi.
Tutto è possibile: L'impossibile richiede solo più tempo
in geometry, angles are angels
"la traslazione non è altro che un'omotetia di centro infinito e k... molto strano"
julio14 ha scritto: jordan è in realtà l'origine e il fine di tutti i mali in $ \mathbb{N} $
ispiratore del BTAEvaristeG ha scritto:Quindi la logica non ci capisce un'allegra e convergente mazza.
in geometry, angles are angels
"la traslazione non è altro che un'omotetia di centro infinito e k... molto strano"