Re: [obm-l] divisibilidade

[Cl�udio \(Pr�tica\)]

Caro Daniel:   Suponhamos que N = A0 + A1*10 + A2*10^2 + A3*10^3 + ...   Usando congru�ncia mod 11 teremos: N = A0 - A1 + A2 - A3 + ...  = (A0 + A2 + ..) - (A1 + A3 + .. ) = 11 - 7 = 4 (mod 11)   Agora, o expoente: (10x+1)^18 = (10x)^18 + 18*(10x)^17 +  ...18*(10x) + 1 = 10y + 1, para um certo natural y.   Pelo Pequeno Teorema de Fermat, se mdc(N,11) = 1, N^10 = 1 (mod 11)   Como N = 4 (mod 11), temos que mdc(N,10) = 1 ==> N^10 = 1 (mod 11) ==> N^(10y) = (N^10)^y = 1^y = 1 (mod 11)  ==> N^(10y+1) = N^(10y) * N = 1 * N = N = 4 (mod 11).   Assim, o resto da divis�o � igual a 4.   Em geral, quando se quer calcular o resto da divis�o de A^B (ou mesmo, A^(B^C)) por algum n�mero, � quase sempre necess�rio usar o Pequeno Teorema de Fermat (se o n�mero � primo), ou sua generaliza��o, o Teorema de Euler, que diz:   Se A e N s�o inteiros com N � positivo e mdc(A,N) = 1 ent�o A^Phi(N) = 1 (mod N), onde Phi(N) � o n�mero de inteiros positivos menores do que N e primos com N.   Um abra�o, Claudio. ----- Original Message ----- From: Daniel Pini To: [EMAIL PROTECTED] Sent: Thursday, December 12, 2002 12:03 AM Subject: [obm-l] divisibilidade Em um n�mero natural N, a soma das ordens �mpares � 7 e a soma das ordens pares � 11. Determine o resto do n�: N^(10x+1)^18 , por 11. (Obs: N pertence N*)   Eu tentando resolver este problema vi que N elevado a um multiplo de 10 deixa resto 5 logo N^(10x+1) deixaria resto 2 . Transfomando N^(10x+1) em M (que deixa resto 2) e procurando o resto de M^18 vi que o resto � 3. Mas a resposta correta � 7. Minha duvida ent�o �: como calcular o resto de um express�o do tipo A^B^C?