Inverso modular

Um inteiro positivo multiplicado pelo seu inverso é sempre igual a 1: 17*(1/17)==1. Na aritmética modular existe um conceito semelhante de inverso, embora, para o módulo m, estejamos restritos aos inteiros de 0 a m-1. O inverso multiplicativo modular de 3 módulo 5 é igual a 2 porque (3*2)%5==1. Outro exemplo: o inverso modular de 17 módulo 1000007 é igual a 58824 porque (17*58824)%1000007==1. O inverso modular, se existir, deve estar sempre no intervalo de 0 a m-1.

Crie uma função que receba como argumentos o inteiro n e o módulo m. A função retornará o inverso modular de n mod m. Se o inverso modular não existir, retorne false.

Exemplos

mod_inv(2, 3) ➞ 2

mod_inv(12, 47) ➞ 4

mod_inv(11, 33) ➞ false

mod_inv(55, 678) ➞ 37

mod_inv(81, 3455) ➞ 2346

Observações

• Alguns casos de teste têm inteiros bastante grandes, então, se você tentar fazer uma busca por força bruta em todo o campo modular, talvez não tenha sucesso devido ao limite de tempo de 12 segundos imposto pelo servidor. Consulte Recursos para obter uma abordagem mais eficiente.
• O inverso modular de um número n módulo m existe somente se n e m forem coprimos (ou seja, não tiverem fatores comuns além de 1).
• Um uso prático do inverso modular está na criptografia de chave pública, como RSA, onde ele pode ser usado para determinar o valor da chave privada.