Even I like the answer of Nautilus, I have a different approach.
In the very first round M isn't important, because you can swap M and X.
So I set M to 1 and want to get the most possible information out of the GCD-Answer. Like Nautilus I came to N = 30 (because of 2*3*5) to "filter" these prime numbers. But this is improvable. I can get out more information if I choose a number beyond 50. (50 because 1+50*z is at maximum 2 times a number from 1 to 100)
If I choose 30 I get 8 possible results for GCD(1+x, 30). For example N = 60 (2*2*3*5) or 72 (2*2*2*3*3) or 96 (2*2*2*2*2*3) would give me 12 different values.
This means: If I can build a binary search for the problem, I will find an answer within 6 rounds. This is a little bit complicated to explain (for me), but there are only 32 different possibilities where the GCD-answer is 1. And Sqrt(32) = 5.6568. This all counts only for the first round. Because if you can eliminate so much branches here, you can maybe get more information in the next rounds.
So first I think about an AI for this, but I don't want to overengineer and just bruteforced it with an algorithm to find a fingerprint in 6 rounds for all 100 X.
6 rounds: (M=1,N=40), (M=2,N=30), (M=3,N=40), (M=4,N=80), (M=5,N=27), (M=6,N=48) gives a fingerprint
This is not all. Because you can eliminate more numbers per round than only 50%, you can build a shorter fingerprint.
5 rounds: (M=1,N=40), (M=2,N=30), (M=3,N=40), (M=4,N=80), (M=6,N=48)