Em ter., 27 de out. de 2020 às 20:50, joao pedro b menezes < [email protected]> escreveu:
> Olá, eu estava fazendo esse exercício : > " . (OBM 2005) Dados os inteiros positivos a, c e o inteiro b, prove que > existe um inteiro positivo x tal que a^x + x ≡ b (mod c)." > > Eu pensei nessa solução, mas eu tenho quase certeza que ela está errada... > > "Primeiramente , suponhamos c primo. Desse modo, se escolhermos x tal que > x ≡ 0 (mod c - 1) , teremos a^x + x ≡ 1 + x <=> x ≡ b - 1 (mod c) (pelo > teorema de fermat) . Teríamos o sistema de congruências: > x ≡ 0 ( mod c) > x ≡ b - 1 (mod c-1) > Como c e c-1 são primos entre sí, pelo teorema chinês do resto esse > sistema infinitas soluções. > Agora, suponhamos c composto. Como um número composto é nada mais que o > produto de uma quantidade finita de primos, podemos chamar todos os primos > divisores de c como p1, p2, p3 ... pn . Forçando x ≡ b - 1 (mod pi) para > qualquer pi divisor primo de c, montamos o sistema de congruências: > x ≡ 0 (mod p1 - 1) > x ≡ b - 1 (mod p1) > ................. > x ≡ 0 (mod pn - 1) > x ≡ b - 1 (mod pn) > Apenas olhando por cima, você não pode ignorar os expoentes da fatoração. Além disso, Euler-Fermat exige que a seja primo com c. > O único empecilho para o teorema é que pj - 1 e ph - 1 ( com j e h > inteiros 1 <= j <= h <= n) possivelmente terão múltiplos em comum. Para > anular esse problema, basta fazer com que x seja múltiplo de p1 - 1, p2 - 1 > ..... pn - 1,e chamando de Z o produto de todos esses números, podemos > construir: > x ≡ b - 1 (mod p1) > x ≡ b - 1( mod p2) > ............ > x ≡ b - 1 (mod pn) > x ≡ 0 (mod Z) > Como p1, p2 , ... pn e Z são primos entre si, o sistema sempre terá > infinitas soluções pelo teorema chinês do resto > Dessa forma, comprovamos o enunciado" > > Se ela estiver errada( o que eu tenho quase certeza) , alguém poderia, por > favor, me falar por que ? > Agradeço pela ajuda e pelo tempo por ler este email gigante kkkk >
