Divisibility of Mersenne numbers?

[morbius27]

Homework Statement

Let M_n= 2^(n) - 1 be the n-th Mersenne number.
a) Show that, if m|n, then M_m|M_n
b) Show that, if m<n and m does not divide n, then GCD(M_n,M_m) = GCD(M_m,M_r) where r is the remainder of n upon division by m
c) Let m,n be arbitrary natural numbers, and let d = GCD(m,n). Using the above results, show that GCD(M_n,M_n) = M_d

2. The attempt at a solution
So I figured out part a quite easily, by letting n=mk and using congruences, but I'm stuck on part b as I am unsure whether this can by proved using only congruences or if I need to incorporate the Euclidean algorithm. Any ideas?

 

[mighty2000]

Hello there! Great job on solving part a, that's a good start. For part b, you can use the Euclidean algorithm to prove it. Here's how you can approach it:

Let m and n be two natural numbers such that m < n and m does not divide n. We can write n = mq + r, where q is the quotient and r is the remainder upon division by m. Since m does not divide n, we know that r is non-zero.

Now, let's consider the GCD of M_n and M_m. By definition, GCD(M_n, M_m) is the largest number that divides both M_n and M_m. We can write M_n = 2^n - 1 and M_m = 2^m - 1. Since m < n, we can express 2^n as (2^m)^q * 2^r. Therefore, M_n can be written as (2^m)^q * 2^r - 1.

Now, let's consider the GCD of M_m and M_r, where r is the remainder of n upon division by m. By definition, GCD(M_m, M_r) is the largest number that divides both M_m and M_r. We can write M_m = 2^m - 1 and M_r = 2^r - 1. Since r is the remainder of n upon division by m, we can express 2^n as (2^m)^q * 2^r. Therefore, M_r can be written as (2^m)^q * 2^r - 1.

Now, we can see that both M_n and M_r have the same form, (2^m)^q * 2^r - 1, which means that they have a common factor of (2^m)^q. Therefore, GCD(M_n, M_m) = GCD(M_m, M_r).

I hope this helps! Let me know if you have any other questions.