J'ai une proposition..

Si on se concentre sur le cas a impair (à partir d'un tel a, tous les entiers de la forme 4a vérifient aussi la propriété), on peut facilement prouver que a est de la forme a = 4c+3.
Avec un raisonnement un peu plus fin, on arrive a pour k assez grand :
si il existe n tel que n²+a multiple de 2^k, alors on peut poser n impair donc n=2b+1 et ainsi :
n²+a = (2b+1)²+(4c+3) = 4b²+4b+4c+4 donc b²+b+c+1 multiple d'une puissance de 2. Cette quantité est donc paire. Or, b²+b = b(b+1) est pair car c'est le produit de deux entiers consécutifs. On en déduit que c+1 est pair donc que c est impair.

Par conséquent, c est impair et a est alors de la forme a = 8c+7.
A partir de là, on peut écrire n²+a de la forme :

(2b+1)²+8c+7 = 4b(b+1) + 8(c+1) = 8( b(b+1)/2 + c+1).
Donc b(b+1)/2 + (c+1) est un multiple d'une puissance de 2.

Pour c fixé, on se pose alors la question: peut-on toujours trouver b tel que b(b+1)/2 donne le multiple voulu, lorsqu'on lui ajoute c+1?

On peut remarquer que b(b+1)/2 est la somme des b premiers entiers. On peut faire tendre b vers l'infini, et il semble qu'on tombe nécessairement sur une bonne valeur pour c fixé...

Tryamori, tu es on ne peut plus proche de la conclusion.

Voila, ça reste à prouver.
Il y a une petite subtilité qui t'a échappé pour l'instant....

La réponse a été longue, ça va être indigeste (ça l'est déjà en fait).
Mais ça confirme le a = 4^d (8c+7).

Par exemple pour d=0 et c=1,  a = 15 et pour tout k on peut trouver le n=2b+1 tel que n²+a est multiple de 2^k :

pour k=0,1,2 c'est trop facile n=1 est trivial.
pour k=3, on peut utiliser la méthode que j'ai décrite. D'abord trouver b en regardant les restes des sommes des premiers entiers modulo 2³=8, et prendre b pour lequel ce reste est égal à 8 - (c+1) = 6. Ici, b=3 convient car 1+2+3=6.
Donc n=2b+1=7 convient.
On vérifie que n²+a = 7²+15 = 49+15 = 64 est bien multiple de 8.
Pour k=4, le même n aurait convenu, mais la même méthode fournit la valeur n=25 et on vérifiera que 25²+23 = 640 = 64*10.
Ainsi de suite...

On observe que l'on peut poser d=1, et prendre une valeur paire de a:
pour a = 60, tous les cas qu'on a étudiés pour 15 vont servir. A chaque k il suffit de prendre le double du n trouvé dans le cas k-2 pour a= 15...

@Vasimolo: c'est la bonne réponse. Le jsutificatif n'est pas si long que ça.

@Tryamori: Il faudrait que tu fasses un résumé, car je n'ai pas compris ton raisonnement final. Si possible, évite les exemples, sauf en illustration du cas général.

Voui...., Vasimolo, tu n'expliques pas trop comment tu choisis m correctement, ni même si m existe toujours. Bien que la suite laisse entendre que tu as compris, je ne suis pas sûr que ce soit carré carré....

Là c'est bon Vasimolo, je suis d'accord. Bravo ! 

Ma formalisation est différente, mais c'est bien la même chose.

Ce n'est pas faux Tryamori.

Peu de réponses pour cette énigme (peut être un peu abstraite ?) mais tout de même des réponses justes.

Je donne ici une méthode de résolution complète un peu différente de ce qui a été fait.

Préparation :
On remplace n² + a par le polynome a * n² + b * n + c, qu'on peut caractériser par le triplet (a,b,c) des coeff de n², n et fixe.
On fait évoluer ce polynome pour qu'il soit, d'étapes en étapes, divisible par 2, en remplaçant n par 2n ou 2n + 1.
Si on remplace n par 2n (a,b,c) devient (4a, 2b, c)
Si on remplace n par 2n+1, (a,b,c) devient (4a, 4a+2b, a+b+c)

Discussion :
On pose c = 2c il faut n = 2n ----> (1,0,2c) devient (4,0,2c), simplifié en (2,0,c)
Si c impair: FIN car (2,0,c) impair quel que soit n.
On pose c = 4c, il faut n = 2n ---> (1,0,4c) devient (4,0,4c), simplifié en (1,0,c) c'est à dire le triplet origine.

Conclusion intermédiaire : si c pair, il faut qu'il soit divisible par une puissance de 4. Et dans ce cas, on se ramène tjs au seul facteur impair.

On pose c = 2c+1, il faut n = 2n + 1 ---->(1,0,2c+1) devient (4, 4, 2c+2) simplifié en (2,2,c+1)
Si c+1 impair : FIN car (2,2, c+1) impair quel que soit n.

On pose c = 4c + 3. il faut n = 2n + 1 -----> (1,0, 4c+3) devient (4,4,4c+4) simplifié en (1,1,c+1)
Si c+1 impair: FIN car (1,1,c+1) est impair quel que soit n.

On pose c = 8c + 7, il faut n = 2n + 1 ----> ( 1, 0, 8c+7) devient (4,4,8c+8) simplifié en ( 1,1, 2c+2)
A partir de ce triplet (1,1,2c+2), c'est toujours bon quel que soit c.
En effet, qu'on remplace n par 2n ou 2n+1, le coeff "a" sera multiplié par 4, alors que le coeff  "b" sera multiplié par 2 seulement ( si b impair, 2b ou 4a+2b n'est pas divisible par 4,seulement par 2).
Donc la simplification du triplet (division par 2) ramènera toujours le coeff "b" à un nombre impair, alors que le coeff "a" restera pair. Et donc la parité du polynome sera celle de b*n + c, avec b impair.
Il suffit de choisir n pair si c pair et n impair si c impair pour faire évoluer le polynome vers une parité aussi grande que l'on veut.

Conclusion finale: Seuls conviennent pour c les nombres de la forme (4^n) * ( 8c + 7)  et aussi le cas particulier 0.

CQFD