Um número de Mersenne é um número na forma de <code>2^P-1</code>. Se P for primo, o número de Mersenne pode ser um primo de Mersenne. (Se P não for primo, o número de Mersenne também não é primo.) Na busca por números primos de Mersenne é vantajoso eliminar expoentes encontrando um fator pequeno antes de iniciar um <a href="https://rosettacode.org/wiki/Lucas-Lehmer test" target="_blank" rel="noopener noreferrer nofollow">teste Lucas-Lehmer</a> que pode ser longo. Existem algoritmos muito eficientes para determinar se um número divide <code>2^P-1</code> (ou equivalentemente, se <code>2^P mod (the number) = 1</code>). Algumas linguagens já possuem implementações integradas desta operação exponente-e-mod (chamada modPow ou algo similar). A seguir, vemos como você mesmo pode implementar este modPow: Por exemplo, vamos calcular <code>2²³ mod 47</code>. Converta o expoente 23 em binário, você obtém 10111. Começando com <code><tt>square</tt> = 1</code>, eleve-o ao quadrado repetidamente. Remova a parte superior do expoente e se for 1 multiplique square pela base da exponenciação (2), depois calcule <code><tt>square</tt> módulo 47</code>. Use o resultado do módulo da última etapa como o valor inicial de square na próxima etapa: <pre>Remove Optional square top bit multiply by 2 mod 47 ------------ ------- ------------- ------ 1*1 = 1 1 0111 1*2 = 2 2 2*2 = 4 0 111 no 4 4*4 = 16 1 11 16*2 = 32 32 32*32 = 1024 1 1 1024*2 = 2048 27 27*27 = 729 1 729*2 = 1458 1 </pre> Como <code>2²³ mod 47 = 1</code>, 47 é um fator de <code>2^P-1</code>. (Para ver isso, subtraia 1 de ambos os lados: <code>2²³-1 = 0 mod 47</code>.) Como mostramos que 47 é um fator, <code>2²³-1</code> não é primo. Outras propriedades dos números de Mersenne nos permitem refinar ainda mais o processo. Qualquer fator q de <code>2^P-1</code> deve ser da forma 2kP+1, sendo k um inteiro positivo ou zero. Além disso, q deve ser 1 ou 7 mod 8. Finalmente, qualquer fator potencial q deve ser <a href="https://rosettacode.org/wiki/Primality_by_trial_division" target="_blank" rel="noopener noreferrer nofollow">primo</a>. Como em outros algoritmos de divisão de teste, o algoritmo termina quando 2kP+1 > sqrt(N). Estes testes só funcionam em números de Mersenne, onde o P é primo. Por exemplo, <code>M₄=15</code> não gera fatores usando essas técnicas, mas se fatoriza em 3 e 5, nenhum dos quais se encaixa em 2kP+1.

Usando o método acima encontre um fator de <code>2^p-1</code>.

Critérios de Aceitação:

Testes:

• `check_mersenne` deve ser uma função.
• `check_mersenne(3)` deve retornar uma string.
• `check_mersenne(3)` deve retornar a string `M3 = 2^3-1 is prime`.
• `check_mersenne(23)` deve retornar a string `M23 = 2^23-1 is composite with factor 47`.
• `check_mersenne(929)` deve retornar a string `M929 = 2^929-1 is composite with factor 13007`.