Menu Close

Question-148157

Tinku Tara 0 Comments
Pin




Question Number 148157 by aliibrahim1 last updated on 25/Jul/21
Answered by puissant last updated on 26/Jul/21
pgcd(a;b)=pgcd(a−b;b) ⇒ pgcd(2^a −1;2^b −1)=pgcd(2^a −2^b ;2^b −1) or 2^a −2^b =2^b (2^(a−b) −1) ⇒pgcd(2^a −1;2^b −1)=pgcd(2^b (2^(a−b) −1);2^b −1) =pgcd(2^(a−b) −1;2^b −1) because 2^b et 2^b −1 first among them.. let a=bq+r ⇒pgcd(2^a −1;2^b −1)=pgcd(2^(a−bq) −1;2^b −1) =pgcd(2^r −1;2^b −1) so pgcd(a−bq;b)=pgcd(r;b) pgcd(a;b)=pgcd(b;r)= ..... =pgcd(r^n ;0) ⇒pgcd(2^a −1;2^b −1)=(2^b −1;2^r −1) = ....... =pgcd(2^r_n −1;2^0 −1)=2^r_n so pgcd(2^a −1;2^b −1)=2^(pgcd(a;b)) −1 puissant....
$$\mathrm{pgcd}\left(\mathrm{a};\mathrm{b}\right)=\mathrm{pgcd}\left(\mathrm{a}−\mathrm{b};\mathrm{b}\right) \\ $$$$\Rightarrow\:\mathrm{pgcd}\left(\mathrm{2}^{\mathrm{a}} −\mathrm{1};\mathrm{2}^{\mathrm{b}} −\mathrm{1}\right)=\mathrm{pgcd}\left(\mathrm{2}^{\mathrm{a}} −\mathrm{2}^{\mathrm{b}} ;\mathrm{2}^{\mathrm{b}} −\mathrm{1}\right) \\ $$$$\mathrm{or}\:\mathrm{2}^{\mathrm{a}} −\mathrm{2}^{\mathrm{b}} =\mathrm{2}^{\mathrm{b}} \left(\mathrm{2}^{\mathrm{a}−\mathrm{b}} −\mathrm{1}\right) \\ $$$$\Rightarrow\mathrm{pgcd}\left(\mathrm{2}^{\mathrm{a}} −\mathrm{1};\mathrm{2}^{\mathrm{b}} −\mathrm{1}\right)=\mathrm{pgcd}\left(\mathrm{2}^{\mathrm{b}} \left(\mathrm{2}^{\mathrm{a}−\mathrm{b}} −\mathrm{1}\right);\mathrm{2}^{\mathrm{b}} −\mathrm{1}\right) \\ $$$$=\mathrm{pgcd}\left(\mathrm{2}^{\mathrm{a}−\mathrm{b}} −\mathrm{1};\mathrm{2}^{\mathrm{b}} −\mathrm{1}\right) \\ $$$$\mathrm{because}\:\mathrm{2}^{\mathrm{b}} \:\mathrm{et}\:\mathrm{2}^{\mathrm{b}} −\mathrm{1}\:\mathrm{first}\:\mathrm{among}\:\mathrm{them}.. \\ $$$$\mathrm{let}\:\mathrm{a}=\mathrm{bq}+\mathrm{r} \\ $$$$\Rightarrow\mathrm{pgcd}\left(\mathrm{2}^{\mathrm{a}} −\mathrm{1};\mathrm{2}^{\mathrm{b}} −\mathrm{1}\right)=\mathrm{pgcd}\left(\mathrm{2}^{\mathrm{a}−\mathrm{bq}} −\mathrm{1};\mathrm{2}^{\mathrm{b}} −\mathrm{1}\right) \\ $$$$=\mathrm{pgcd}\left(\mathrm{2}^{\mathrm{r}} −\mathrm{1};\mathrm{2}^{\mathrm{b}} −\mathrm{1}\right) \\ $$$$\mathrm{so}\:\mathrm{pgcd}\left(\mathrm{a}−\mathrm{bq};\mathrm{b}\right)=\mathrm{pgcd}\left(\mathrm{r};\mathrm{b}\right) \\ $$$$\mathrm{pgcd}\left(\mathrm{a};\mathrm{b}\right)=\mathrm{pgcd}\left(\mathrm{b};\mathrm{r}\right)=\:…..\:=\mathrm{pgcd}\left(\mathrm{r}^{\mathrm{n}} ;\mathrm{0}\right) \\ $$$$\Rightarrow\mathrm{pgcd}\left(\mathrm{2}^{\mathrm{a}} −\mathrm{1};\mathrm{2}^{\mathrm{b}} −\mathrm{1}\right)=\left(\mathrm{2}^{\mathrm{b}} −\mathrm{1};\mathrm{2}^{\mathrm{r}} −\mathrm{1}\right) \\ $$$$=\:…….\:=\mathrm{pgcd}\left(\mathrm{2}^{\mathrm{r}_{\mathrm{n}} } −\mathrm{1};\mathrm{2}^{\mathrm{0}} −\mathrm{1}\right)=\mathrm{2}^{\mathrm{r}_{\mathrm{n}} } \\ $$$$ \\ $$$$\mathrm{so}\:\mathrm{pgcd}\left(\mathrm{2}^{\mathrm{a}} −\mathrm{1};\mathrm{2}^{\mathrm{b}} −\mathrm{1}\right)=\mathrm{2}^{\mathrm{pgcd}\left(\mathrm{a};\mathrm{b}\right)} −\mathrm{1} \\ $$$$ \\ $$$$\:\:\:\:\:\:\:\:\:\:\:\:\mathrm{puissant}…. \\ $$

Pin

Leave a Reply

Your email address will not be published. Required fields are marked *