Facile gcd (addirittura MEMO 2008!)
Facile gcd (addirittura MEMO 2008!)
Trovare tutti i $ k \in \mathbb{Z} $ tali che $ \forall n \in \mathbb{N} $ si abbia che $ 4n+1 $ e $ kn+1 $ non hanno divisori in comune.
The only goal of science is the honor of the human spirit.
Allora è ben evidente che $ (4n+1; kn+1)=(4n+1;(k-4)n) $ è altrettanto immediato notare che poichè $ ((4n+1),n)=1 $ allora $ (4n+1;(k-4)n)=(4n+1,(k-4)) $ ma ora si tratta di vedere che numeri primi p soddisfano $ 4n+1 \equiv 0 \pmod p $ beh sappiamo che per ogni primo p diverso da 2 $ (4,p)=1 $ ne segue che esiste l'inverso di 4 modulo p per ogni primo p diverso da 2.Ma dunque basta prendere l'opposto di tale inverso per avere la soluzione a $ 4n \equiv{-1} \pmod p $. Dunque abbiamo che $ k=2^j+4 $ ,per ogni j naturale oppure $ k=-2^j+4 $ per ogni j naturale sono le sole soluzioni possibili. The End...
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"
Soluzione alternativa:
inizialmente procedo come Carlein, arrivando a dire che $ (4n+1,kn+1)=(4n+1,k-4)=1 $. Dobbiamo quindi trovare dei k tali che per ogni n si abbia che il MCD tra $ 4n+1 $ e $ k-4 $ sia sempre 1. I numeri della forma $ 4n+1 $, sono tutti i dispari $ \equiv 1 \pmod 4 $ , ma i dispari che non sono compresi sono quindi $ \equiv 3 \pmod 4 $ cioè in pratica moltiplicandoli per 3 sono anch'essi della forma $ 4n+1 $. In definitiva $ k-4 $ non può contenere nella fattorizzazione un numero dispari perchè ci sarà sempre un numero della forma $ 4n+1 $ che conterrà al suo interno quel dispari. Quindi $ k-4 $ può essere solo una potenza di 2, cioè $ k-4=2^j\Rightarrow k=2^j+4 $ oppure, se k è negativo $ -k-4=-2^j\Rightarrow -k=-2^j+4 $
inizialmente procedo come Carlein, arrivando a dire che $ (4n+1,kn+1)=(4n+1,k-4)=1 $. Dobbiamo quindi trovare dei k tali che per ogni n si abbia che il MCD tra $ 4n+1 $ e $ k-4 $ sia sempre 1. I numeri della forma $ 4n+1 $, sono tutti i dispari $ \equiv 1 \pmod 4 $ , ma i dispari che non sono compresi sono quindi $ \equiv 3 \pmod 4 $ cioè in pratica moltiplicandoli per 3 sono anch'essi della forma $ 4n+1 $. In definitiva $ k-4 $ non può contenere nella fattorizzazione un numero dispari perchè ci sarà sempre un numero della forma $ 4n+1 $ che conterrà al suo interno quel dispari. Quindi $ k-4 $ può essere solo una potenza di 2, cioè $ k-4=2^j\Rightarrow k=2^j+4 $ oppure, se k è negativo $ -k-4=-2^j\Rightarrow -k=-2^j+4 $
"fatti non foste a viver come bruti,
ma per seguir virtute e canoscenza"(Dante)
ma per seguir virtute e canoscenza"(Dante)
Scusate ma non capisco questo passaggio...Carlein ha scritto:Allora è ben evidente che $ (4n+1; kn+1)=(4n+1;(k-4)n) $
...
Qualcuno me lo potrebbe spiegare??"Quando un uomo siede un'ora in compagnia di una bella ragazza, sembra sia passato un minuto. Ma fatelo sedere su una stufa per un minuto e gli sembrerà più lungo di qualsiasi ora. Questa è la relatività." (Albert Einstein)
Ok, grazie... Mi mancava questo pezzo..String ha scritto:Dati due interi a e b, $ (a,b)=(a,b-a)=(a,b+a)=(a,b+ka) $. In questo caso, $ a=4n+1 $e $ b=kn+1 $. Dato che $ (a,b)=(a,b-a) $ abbiamo che $ (4n+1,kn+1)=(4n+1,(k-4)n) $
"Quando un uomo siede un'ora in compagnia di una bella ragazza, sembra sia passato un minuto. Ma fatelo sedere su una stufa per un minuto e gli sembrerà più lungo di qualsiasi ora. Questa è la relatività." (Albert Einstein)