Can two Mersenne numbers share a factor?

[science_man_88]

Originally Posted by R.D. Silverman

Hint: GCD(A,B) = GCD(A-B, B). use descent.

if I understand what was said correctly:

GCD(A,B) = GCD(A-B,B) = GCD(A-xB,B)

[only_human]

Originally Posted by R.D. Silverman

Hint: GCD(A,B) = GCD(A-B, B). use descent.

I follow that and appreciate the help. I know that the a divisor of A and B is also a divisor of their difference. Also I follow that the difference is smaller than one of the two original values can be used in second GCD step as you've just hinted and a new, smaller difference can be calculated until a 0 or 1 is reached (if 0, the previous value is the GCD) and that Euclid originally used subtraction and the modern way is to do a divide or better yet a Mod operation because only the remainder is needed.

What is actually holding me back is my wondering about something else...

See, the point of using repunits is actually to do a kind of arithmetic rather than even algebra. Proofs and things are much easier with algebra and the reason for drawing the strings of 1s has grown to seem almost pointless to me. It just gives a recognizable symbol in each position of a positional representation system even when working with different bases but it is a little like discussing the adjustment and comfort of a car seat versus the utility of actually driving.

So I have been asking myself why I am even doing this; and I have even worked out schoolboy mathematics to see that I could do a schoolboy divide of one repunit by another and end up with a quotient that I wouldn't care about and a remainder repunit that could be used for a Mod operation and this gives me insight into the form of a remainder because it is always a repunit if there is a remainder. But really, working with a repunit is silly here because it would work identically even if the 1s were some other value, like 9s; if the symbol matches in each position between divisor and dividend, it doesn't matter much what the value is. It is a specificity that loses possibly desired generality.

It would be easier to use properties of the GCD function (multiplicative, commutative, associative, etc.) to derive why GCD(bⁿ-1,b^m-1) = b^GCD(m,n)-1

I did look at one proof of GCD(2ⁿ-1,2^m-1) = 2^GCD(m,n)-1 and it depended on using the Extended Euclidean Algorithm to get the coefficients to make a linear combination that = 1 ... and I didn't like it because if working as algebraically as that, there is hardly any point in framing anything in repunits at all.

So if not framing the work with repunits, then I really feel awkward because I have been adjusting the seat on the car instead of driving anywhere. Here are my verbose thoughts on the matter from a day or so ago but I think I should just drop the direction of it all and look over the thread and see what I really don't understand and just go directly at that rather than twiddling around:

The greatest number that represented in standard positional notation for n positions to an arbitrary base is bⁿ - 1. Dividing through by b - 1 results a sequence of n 1s (repunit). Thus the exponent n always matches the corresponding repunit length.

With schoolboy division of a repunit by another repunit, only 0s and 1s are needed because if the divisor is smaller, a 1 is written to the quotient and the divisor is subtracted from the most significant part end of the dividend repunit (resulting in 0s), then 0s are appended to the quotient for each position needed to slide the divisor to the right until it can again be subtracted from the dividend. If the divisor is larger than what is the remainder of the dividend, then what remains is be called the remainder and a length of 0s corresponding to the length of the remainder is appended to the quotient.

The remainder is itself a repunit because division results in exact subtractions of 1s of the divisor from 1s of the dividend with no borrows occurring; the remainder, if any, is from the least significant portion of the dividend that was left over after subtracting multiple lengths of the divisor from the dividend starting at the most significant end.

A mod operation would only care about the remainder from the division operation and the quotient could be neglected.

I just need to study more at this point I think.

[wblipp]

Originally Posted by only_human

I just need to study more at this point I think.

Yes, and you are crossing an important threshold of mathematical maturity here. You are grasping how the algebra says the same things that the arithmetic said, but also brings more powerful tools to the discussion. Much of mathematics is about finding more powerful generalizations that enlighten understanding of the old topic and open new fields (pun intended) of study that are themselves eventually generalized in new directions.