Menu Close

proof-gcd-2-m-1-2-n-1-2-gcd-m-n-1-

Tinku Tara 0 Comments
Pin




Question Number 223346 by cryptograph last updated on 21/Jul/25
proof gcd(2^m −1,2^n −1)=2^(gcd(m,n)) −1
$${proof}\:{gcd}\left(\mathrm{2}^{{m}} −\mathrm{1},\mathrm{2}^{{n}} −\mathrm{1}\right)=\mathrm{2}^{{gcd}\left({m},{n}\right)} −\mathrm{1} \\ $$
Answered by Raphael254 last updated on 22/Jul/25
if m = kn, k ∈ Z^∗ : gcd(m,n) = gcd(n,m) = ∣n∣ if m ≠ kn, k ∈ Z^∗ : gcd(m,n) = gcd(n,m) = 1 2^m −1, m ∈ N^∗ is a odd and integer number 2^n −1, n ∈ N^(∗ ) is a odd and integer number Consider m, n ∈ N^∗ : if m = kn, k ∈ N^∗ : gcd(m,n) = gcd(n,m) = n (∗) if m ≠ kn, k ∈ N^∗ : gcd(m,n) = gcd(n,m) = 1 (∗∗) For (∗): gcd(2^m − 1, 2^(gcd(m,n)) − 1) = 2^n −1 2^m − 1 = k(2^(gcd(m,n)) − 1) k = ((2^m − 1)/(2^(gcd(m,n)) − 1)) = (((2^n )^(m/n) − 1 )/(2^n − 1)) (((2^n )^(m/n) − 1)/(2^n − 1)) = (2^n )^((m/n) − 1) + (2^n )^((m/n) − 2) + (2^n )^((m/n) − 3) + ... + (2^n )^((m/n) − (m/n)) = Σ_(i = 1 ) ^(m/n) (2^n )^((m/n) − i) It is proved that ∃k ∈ N^∗ that satisfies 2^m − 1 = k(2^(gcd(m,n)) − 1) with m,n ∈ N^∗ So: gcd(2^m − 1, 2^n − 1) = 2^(gcd(m,n)) − 1 Now, for (∗∗): gcd(2^m − 1, 2^n − 1) = 2^1 − 1 gcd(2^m − 1, 2^n − 1) = 1 How we assumed that gcd(m,n) = 1: 2^m − 1 ≠ k(2^n − 1), because: ∄k ∈ N^∗ with m,n ∈ N^∗ that satisfies k = ((2^m − 1)/(2^n − 1)), because: ((2^m − 1)/(2^n − 1)) = 2^(m − n) + 2^(m − 2n) + 2^(m − 3n) + ... (when 2^p of the quotient < 2^n of the divisor, that occurs after 2^p appears in the quotient the integer quotient (m/n) times) ... + ((2^p −1)/2^n ) + ((2^p − 1)/2^(2n) ) + ((2^p − 1)/2^(3n) ) + ((2^p − 1)/2^(a×n) ), where a ∈ N^∗ = Σ_(i = 1) ^(m/n) 2^(m − i×n) + Σ_(i = 1) ^a ((2^p − 1)/2^(i×n) ) See that after the first sum, all the others numbers are not integers, so ∄k ∈ N^∗ So we can confirm that: gcd(2^m − 1, 2^n − 1) = 1 How we proved (∗) and (∗∗), so: gcd(2^m − 1, 2^n − 1) = 2^(gcd(m,n)) − 1 In the demonstration we took m ≥ n. But in a similar way, we can prove all of this to m < n.
$${if}\:{m}\:=\:{kn},\:{k}\:\in\:\mathbb{Z}^{\ast} : \\ $$$$ \\ $$$${gcd}\left({m},{n}\right)\:=\:{gcd}\left({n},{m}\right)\:=\:\mid{n}\mid \\ $$$$ \\ $$$${if}\:{m}\:\neq\:{kn},\:{k}\:\in\:\mathbb{Z}^{\ast} : \\ $$$$ \\ $$$${gcd}\left({m},{n}\right)\:=\:{gcd}\left({n},{m}\right)\:=\:\mathrm{1} \\ $$$$ \\ $$$$\mathrm{2}^{{m}} −\mathrm{1},\:{m}\:\in\:\mathbb{N}^{\ast} \:{is}\:{a}\:{odd}\:{and}\:{integer}\:{number} \\ $$$$\mathrm{2}^{{n}} −\mathrm{1},\:{n}\:\in\:\mathbb{N}^{\ast\:} {is}\:{a}\:{odd}\:{and}\:{integer}\:{number} \\ $$$$ \\ $$$${Consider}\:{m},\:{n}\:\in\:\mathbb{N}^{\ast} : \\ $$$$ \\ $$$${if}\:{m}\:=\:{kn},\:{k}\:\in\:\mathbb{N}^{\ast} : \\ $$$$ \\ $$$${gcd}\left({m},{n}\right)\:=\:{gcd}\left({n},{m}\right)\:=\:{n}\:\left(\ast\right) \\ $$$$ \\ $$$${if}\:{m}\:\neq\:{kn},\:{k}\:\in\:\mathbb{N}^{\ast} : \\ $$$$ \\ $$$${gcd}\left({m},{n}\right)\:=\:{gcd}\left({n},{m}\right)\:=\:\mathrm{1}\:\left(\ast\ast\right) \\ $$$$ \\ $$$${For}\:\left(\ast\right): \\ $$$$ \\ $$$${gcd}\left(\mathrm{2}^{{m}} \:−\:\mathrm{1},\:\mathrm{2}^{{gcd}\left({m},{n}\right)} \:−\:\mathrm{1}\right)\:=\:\mathrm{2}^{{n}} \:−\mathrm{1} \\ $$$$ \\ $$$$\mathrm{2}^{{m}} \:−\:\mathrm{1}\:=\:{k}\left(\mathrm{2}^{{gcd}\left({m},{n}\right)} \:−\:\mathrm{1}\right) \\ $$$$ \\ $$$${k}\:=\:\frac{\mathrm{2}^{{m}} \:−\:\mathrm{1}}{\mathrm{2}^{{gcd}\left({m},{n}\right)} \:−\:\mathrm{1}}\:=\:\frac{\left(\mathrm{2}^{{n}} \right)^{\frac{{m}}{{n}}} \:−\:\mathrm{1}\:}{\mathrm{2}^{{n}} \:−\:\mathrm{1}} \\ $$$$ \\ $$$$\frac{\left(\mathrm{2}^{{n}} \right)^{\frac{{m}}{{n}}} −\:\mathrm{1}}{\mathrm{2}^{{n}} \:−\:\mathrm{1}}\:=\:\left(\mathrm{2}^{{n}} \right)^{\frac{{m}}{{n}}\:−\:\mathrm{1}} \:+\:\left(\mathrm{2}^{{n}} \right)^{\frac{{m}}{{n}}\:−\:\mathrm{2}} +\:\left(\mathrm{2}^{{n}} \right)^{\frac{{m}}{{n}}\:−\:\mathrm{3}} +\:…\:+\:\left(\mathrm{2}^{{n}} \right)^{\frac{{m}}{{n}}\:−\:\frac{{m}}{{n}}} \:=\:\underset{{i}\:=\:\mathrm{1}\:} {\overset{\frac{{m}}{{n}}} {\sum}}\left(\mathrm{2}^{{n}} \right)^{\frac{{m}}{{n}}\:−\:{i}} \\ $$$$ \\ $$$${It}\:{is}\:{proved}\:{that}\:\exists{k}\:\in\:\mathbb{N}^{\ast} \:{that}\:{satisfies}\:\mathrm{2}^{{m}} \:−\:\mathrm{1}\:=\:{k}\left(\mathrm{2}^{{gcd}\left({m},{n}\right)} \:−\:\mathrm{1}\right)\:{with}\:{m},{n}\:\in\:\mathbb{N}^{\ast} \\ $$$$ \\ $$$${So}: \\ $$$$ \\ $$$${gcd}\left(\mathrm{2}^{{m}} \:−\:\mathrm{1},\:\mathrm{2}^{{n}} −\:\mathrm{1}\right)\:=\:\mathrm{2}^{{gcd}\left({m},{n}\right)} \:−\:\mathrm{1} \\ $$$$ \\ $$$${Now},\:{for}\:\left(\ast\ast\right): \\ $$$$ \\ $$$${gcd}\left(\mathrm{2}^{{m}} \:−\:\mathrm{1},\:\mathrm{2}^{{n}} \:−\:\mathrm{1}\right)\:=\:\mathrm{2}^{\mathrm{1}} \:−\:\mathrm{1} \\ $$$${gcd}\left(\mathrm{2}^{{m}} \:−\:\mathrm{1},\:\mathrm{2}^{{n}} \:−\:\mathrm{1}\right)\:=\:\mathrm{1} \\ $$$$ \\ $$$${How}\:{we}\:{assumed}\:{that}\:{gcd}\left({m},{n}\right)\:=\:\mathrm{1}: \\ $$$$ \\ $$$$\mathrm{2}^{{m}} \:−\:\mathrm{1}\:\neq\:{k}\left(\mathrm{2}^{{n}} \:−\:\mathrm{1}\right),\:{because}: \\ $$$$ \\ $$$$\nexists{k}\:\in\:\mathbb{N}^{\ast} \:{with}\:{m},{n}\:\in\:\mathbb{N}^{\ast} \:{that}\:{satisfies}\:{k}\:=\:\frac{\mathrm{2}^{{m}} \:−\:\mathrm{1}}{\mathrm{2}^{{n}} \:−\:\mathrm{1}},\:{because}: \\ $$$$\frac{\mathrm{2}^{{m}} \:−\:\mathrm{1}}{\mathrm{2}^{{n}} \:−\:\mathrm{1}}\:=\:\mathrm{2}^{{m}\:−\:{n}} \:+\:\mathrm{2}^{{m}\:−\:\mathrm{2}{n}} \:+\:\mathrm{2}^{{m}\:−\:\mathrm{3}{n}} \:+\:…\:\left({when}\:\mathrm{2}^{{p}} \:{of}\:{the}\:{quotient}\:<\:\mathrm{2}^{{n}} \:{of}\:{the}\:{divisor},\:{that}\:{occurs}\:{after}\:\mathrm{2}^{{p}} \:{appears}\:{in}\:{the}\:{quotient}\:{the}\:{integer}\:{quotient}\:\frac{{m}}{{n}}\:{times}\right)\:…\:+\:\frac{\mathrm{2}^{{p}} −\mathrm{1}}{\mathrm{2}^{{n}} }\:+\:\frac{\mathrm{2}^{{p}} \:−\:\mathrm{1}}{\mathrm{2}^{\mathrm{2}{n}} }\:+\:\frac{\mathrm{2}^{{p}} \:−\:\mathrm{1}}{\mathrm{2}^{\mathrm{3}{n}} }\:+\:\frac{\mathrm{2}^{{p}} \:−\:\mathrm{1}}{\mathrm{2}^{{a}×{n}} },\:{where}\:{a}\:\in\:\mathbb{N}^{\ast} \:=\:\underset{{i}\:=\:\mathrm{1}} {\overset{\frac{{m}}{{n}}} {\sum}}\:\mathrm{2}^{{m}\:−\:{i}×{n}} \:+\:\underset{{i}\:=\:\mathrm{1}} {\overset{{a}} {\sum}}\frac{\mathrm{2}^{{p}} \:−\:\mathrm{1}}{\mathrm{2}^{{i}×{n}} } \\ $$$$\: \\ $$$${See}\:{that}\:{after}\:{the}\:{first}\:{sum},\:{all}\:{the}\:{others}\:{numbers}\:{are}\:{not}\:{integers},\:{so}\:\nexists{k}\:\in\:\mathbb{N}^{\ast} \\ $$$$ \\ $$$${So}\:{we}\:{can}\:{confirm}\:{that}: \\ $$$$ \\ $$$${gcd}\left(\mathrm{2}^{{m}} \:−\:\mathrm{1},\:\mathrm{2}^{{n}} \:−\:\mathrm{1}\right)\:=\:\mathrm{1} \\ $$$$ \\ $$$${How}\:{we}\:{proved}\:\left(\ast\right)\:{and}\:\left(\ast\ast\right),\:{so}: \\ $$$$ \\ $$$${gcd}\left(\mathrm{2}^{{m}} \:−\:\mathrm{1},\:\mathrm{2}^{{n}} \:−\:\mathrm{1}\right)\:=\:\mathrm{2}^{{gcd}\left({m},{n}\right)} \:−\:\mathrm{1} \\ $$$$ \\ $$$${In}\:{the}\:{demonstration}\:{we}\:{took}\:{m}\:\geq\:{n}. \\ $$$${But}\:{in}\:{a}\:{similar}\:{way},\:{we}\:{can}\:{prove}\:{all}\:{of}\:{this}\:{to}\:{m}\:<\:{n}. \\ $$

Pin

Leave a Reply

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