Linked Questions

17
votes
2answers
7k views

$\gcd(b^x - 1, b^y - 1, b^ z- 1,\dots) = b^{\gcd(x, y, z,\dots)} -1$ [duplicate]

Possible Duplicate: Prove that $\gcd(a^n - 1, a^m - 1) = a^{\gcd(n, m)} - 1$ $b$, $x$, $y$, $z$, $\ldots$ are integers greater than 1. How can we prove that $$ \gcd (b ^ x - 1, b ^ y - 1, b ^ z - ...
5
votes
3answers
7k views

Prove that if $d$ divides $n$, then $2^d -1$ divides $2^n -1$ [duplicate]

Prove that if $d$ divides $n$, then $2^d -1$ divides $2^n -1$. Use the identity $x^k -1 = (x-1)*(x^{k-1} + x^{k-2} + \cdots + x +1)$
4
votes
2answers
3k views

Gcd number theory proof: $(a^n-1,a^m-1)= a^{(m,n)}-1$ [duplicate]

Prove that if $a>1$ then $(a^n-1,a^m-1)= a^{(m,n)}-1$ where $(a,b) = \gcd(a,b)$ I've seen one proof using the Euclidean algorithm, but I didn't fully understand it because it wasn't very well ...
0
votes
3answers
2k views

GCD of two big numbers [duplicate]

How to find $gcd(5^{100}-1, 5^{120}-1)$? The problem is numbers are really big ($5^{100}$ is 70 digits). None of the numbers is prime. I ran Euclid's algorithm on Python and found the answer in less ...
3
votes
0answers
2k views

Show that $\gcd(2^m-1, 2^n-1) = 2^ {\gcd(m,n)} -1$ [duplicate]

Possible Duplicate: Prove that $\gcd(a^n - 1, a^m - 1) = a^{\gcd(n, m)} - 1$ $\gcd(b^x - 1, b^y - 1, b^ z- 1,…) = b^{\gcd(x, y, z,…)} -1$ I'm trying to figure this out: ...
1
vote
1answer
2k views

Prove: $\gcd(n^a-1,n^b-1)=n^{\gcd(a,b)}-1$ [duplicate]

I'm trying to prove the following statement: $$\forall_{a,b\in\Bbb{N^{+}}}\gcd(n^a-1,n^b-1)=n^{\gcd(a,b)}-1$$ As for now I managed to prove that $n^{\gcd(a,b)}-1$ divdes $n^a-1$ and $n^b-1$: Without ...
2
votes
1answer
1k views

Greatest common divisor of $X^n-1$ and $X^m-1$ [duplicate]

Let $f=X^n-1$ and $g=X^m-1$ be two polynomials. Show that: $$\left(f,g\right)=X^{\left(n,m\right)}-1,$$ where $\left(a,b\right)=$ greatest common divisor of $a$ and $b$.
-1
votes
1answer
556 views

Computing $\gcd$ of very large numbers with powers [duplicate]

How to calculate $\gcd$ of $5^{2^{303} - 1} - 1$ and $5^{2^{309} - 1} - 1$? I stumbled upon this interesting problem and tried elementary algebraic simplification and manipulation. But found no ...
-2
votes
1answer
402 views

number theory division of power for the case $(n^r −1)$ divides $(n^m −1)$ if and only if $r$ divides $m$. [duplicate]

Let $n > 1$ and $m$ and $r$ be positive integers. Prove that $(n^r −1)$ divides $(n^m −1)$ if and only if $r$ divides $m$.
2
votes
1answer
553 views

Prove $\gcd(k, l) = d \Rightarrow \gcd(2^k - 1, 2^l - 1) = 2^d - 1$ [duplicate]

This is a problem for a graduate level discrete math class that I'm hoping to take next year (as a senior undergrad). The problem is as stated in the title: Given that $\gcd(k, l) = d$, prove that $...
1
vote
1answer
315 views

GCD of two polynomials in Mod 2 [duplicate]

Possible Duplicate: Prove that $\gcd(a^n - 1, a^m - 1) = a^{\gcd(n, m)} - 1$ Let $p$ and $q$ be distinct primes. I wonder is the following statement always true? $$\gcd(x^p-1, x^q-1) \stackrel{?}...
1
vote
2answers
301 views

prove that $2^{35}-1$ is divisible by 31 and 127 [duplicate]

Can you give me a hint to how to approach the problem.How one can show that $2^{35}-1$ is a multiple of 31 and 127?
0
votes
1answer
265 views

Prove that GCD$(n^a - 1,n^b -1)= n^{GCD(a,b)} -1$ [duplicate]

I used Euclid's theorem $a=bq +r$. $n^a -1 = ((n^b)^q )n^r -1$ I don't know how to move forward.
1
vote
3answers
55 views

Proof that $(2^{17}-1)(2^{71}-1)$ divides $2^{1207}-1$ [duplicate]

$(2^{17}-1)(2^{71}-1)$ divides $2^{1207}-1$. How can we prove it elegantly? Related: given odd $k$, if there a way to predict the $j$ such that $2^j-1$ divides $2^k-1$, short of trying?
0
votes
1answer
89 views

Greatest common divisor of $(2^{21}-1,2^{27}-1)$ [duplicate]

Find $\text{gcd}(2^{21}-1,2^{27}-1).$ My proof: We know that $2^{21}-1=(2^3)^7-1=8^7-1=(8-1)(8^6+\dots+8+1)=7(8^6+\dots+8+1)=7N_1$ and $2^{27}-1=(2^3)^9-1=8^9-1=(8-1)(8^8+\dots+8+1)=7(8^8+\dots+8+1)=...

15 30 50 per page
1
2 3 4 5
10