I solved the first part of this problem. I can prove that n must be of the form 2 ^ k: it is a necessary condition and I found the minimum values of a for n = 2, 4, 8, 16 and 32. This last value is enormous (a=2802887184). I will write the detailed demonstration when I have a little time.

But I still can't prove that the condition n=2^k is sufficient, especially since the demonstration must involve modular arithmetic with Fermat's numbers as bases and that the next one (F5) is not prime unlike F0 -> F4.

The problem is very interesting and if a real mathematician (I'm not) goes through here, it would be nice to help us.

PS : Apologize for my mistakes in english (I'm a french speaker)

None of the Mersenne's numbers (2^n-1) where n is of the form 2^k has prime factors of the form 4k-1 (easy to demonstrate).

You can see below that all the others seem to have at least one (in red), but I can't prove it. There is a periodicity for some factors (like 7, 11, 17, 31, ...) but I don't see yet the general rule.

I will read this later and thanks for that solution :)

Below the answer with the complete proof. Don't hesitate to correct if you see any error. PDF avalaible on demand.

I can now put words on the last question to solve :

" Is (-9) a quadratic residue mod F(k) for all k ? If not, for which ?"

(F(k) is the k-th Fermat's number)

The answer is "yes" for k=0 to 4 but beyond ...

Okay i put that problem Theresa because i round that intersting but i cant prouve it and im glad that you liked it, im french too by the way

I solved the first part of this problem. I can prove that n must be of the form 2 ^ k: it is a necessary condition and I found the minimum values of a for n = 2, 4, 8, 16 and 32. This last value is enormous (a=2802887184). I will write the detailed demonstration when I have a little time.

But I still can't prove that the condition n=2^k is sufficient, especially since the demonstration must involve modular arithmetic with Fermat's numbers as bases and that the next one (F5) is not prime unlike F0 -> F4.

The problem is very interesting and if a real mathematician (I'm not) goes through here, it would be nice to help us.

PS : Apologize for my mistakes in english (I'm a french speaker)

So, two major tasks remain :

* prove that all the M(n) have "bad" prime factor except if n=2^k

* show that the absence of "bad" prime factor is not only a necessary condition (proven), but also a sufficient condition.

This is not sure : using a spreadsheet, I found a valid "a" for n=2, 4, 8 and 16 but not for n=32 (if it exists a is > 27974916)

None of the Mersenne's numbers (2^n-1) where n is of the form 2^k has prime factors of the form 4k-1 (easy to demonstrate).

You can see below that all the others seem to have at least one (in red), but I can't prove it. There is a periodicity for some factors (like 7, 11, 17, 31, ...) but I don't see yet the general rule.

A possible approach :

- a²+9 is a sum of two squares

- a prime of the form 4k-1 divides the sum only if it divides both squares (Euler)

- the only prime of the form 4k-1 that divides 9 is 3

- so, the dividor 2^n-1 of your problem must have only prime factors of the form 4k+1 except 3.

All for now. I follow this track tonight.