Mostrando postagens com marcador Números Inteiros. Mostrar todas as postagens
Mostrando postagens com marcador Números Inteiros. Mostrar todas as postagens

Exercício Resolvido - Inteiros de Gauss

O exercício resolvido neste post será o Problema 1 do capítulo "Inteiros de Gauss" do arquivo disponível no link http://www.obm.org.br/export/sites/default/revista_eureka/docs/artigos/gauss.doc escrito por Guilherme Fujiwara.
Deste arquivo irei transcrever algumas definições e teoremas, conforme eles forem sendo usados, porém não serão disponibilizadas aqui as provas dos teoremas. Estas podem ser vistas no próprio documento.

Problema 1. Determine todos os pares x, y Î Z tal que y³ = x² + 1.


Solução:
y³ = x² + 1
y³ = (x + i)*(x - i)
onde
i² = -1.

INTEIROS DE GAUSS
Definimos o conjunto Z[i] dos inteiros de Gauss como Z[i] = {a + bi | a, b Є Z}, onde (i² = –1).
Fatoração única
Todo inteiro z de Gauss com norma maior que 1 pode ser escrito como o produto de um ou mais primos de Gauss. Além disso, esta fatoração é única.

Desta forma, como desejamos soluções pertencentes a Z para x e y, então (x + i) e (x - i) são inteiros de Gauss. Portanto, pela propriedade da fatoração única, cada um deles pode ser escrito como o produto de primos de Gauss, onde um primo de Gauss é definido por ser um inteiro de Gauss que não pode ser escrito pelo produto de dois inteiros de Gauss não unitários.

Assim:

(x + i) = (α1)¹*(α2)²*(α3)³*...*(αk1)ᵏ¹
(x - i) = (β1)ᵇ¹*(β2)ᵇ²*(β3)ᵇ³*...*(βk2)ᵇᵏ²
onde αn e βn são primos de Gauss e an e bn são os expoentes dos termos da fatoração.

Da fatoração acima, será necessário saber se existe algum α ou β iguais, ou seja, se algum dos primos da fatoração de (x + i) é igual a algum dos primos da fatoração de (x - i). O que se pode deduzir é que, se existe algum termo das fatorações de ambos que sejam iguais, então este primo também é um termo na fatoração de qualquer combinação aritmética (soma, subtração, divisão e multiplicação) entre eles.
Fazendo:
(x + i) - (x - i) = 2i
(x + i) + (x - i) = 2x
Portanto, caso exista algum α que seja igual a algum β, este é 2 (ou 2i, ou -2, ou -2i), já que as unidades dos inteiros de Gauss são 1, -1, i e -i.

Obs.: É importante perceber que o 2 não é, necessariamente, um termo da fatoração. O que se ressalta aqui é que se o 2 for termo da fatoração de um deles, então é dos dois e neste caso este seria o único termo em comum na fatoração de (x + i) e (x - i). Logo, qualquer α é diferente de qualquer β, exceto se um deles for 2.

Porém, da divisibilidade temos que:

Divisibilidade
Dizemos que para a, b Є Z[i], a|b (lê-se a divide b) se ƎЄ Z[i] tal que b = ac.

Logo, se 2ᵏ é fator da decomposição de (x + i), então existe um c = (a + bi) (inteiro de Gauss) tal que:
x + i = 2ᵏ*(a + bi)
x + i = 2ᵏ*a + 2ᵏ*bi
Ou seja:
2ᵏ*b = 1. Mas como b é um inteiro, então k = 0.

Portanto, a equação inicial fica:
y³ = [(α1)¹*(α2)²*(α3)³*...*(αk1)ᵏ¹]*[(β1)ᵇ¹*(β2)ᵇ²*(β3)ᵇ³*...*(βk2)ᵇᵏ²]

Porém, para que y seja inteiro, cada um dos expoentes a1, a2, a3, ..., ak1 e b1, b2, b3, ..., bk2 devem ser múltiplos de 3, já que todos os primos de Gauss α e β são diferentes. Desta forma podemos escrever a equação:
y³ = [(α1)¹'*(α2)²'*(α3)³'*...*(αk1)ᵏ¹'*(β1)ᵇ¹'*(β2)ᵇ²'*(β3)ᵇ³'*...*(βk2)ᵇᵏ²']³
Além disso:
(x + i) =  [(α1)¹'*(α2)²'*(α3)³'*...*(αk1)ᵏ¹']³
e
(x - i) = [(β1)ᵇ¹'*(β2)ᵇ²'*(β3)ᵇ³'*...*(βk2)ᵇᵏ²']³
Usando:
1)¹'*(α2)²'*(α3)³'*...*(αk1)ᵏ¹' = u + vi
Onde u + vi é um inteiro de Gauss.

Assim:
(x + i) = (u + vi)³ = [u³ + 3u²vi + 3u(vi)² + (vi)³] = u³ + 3u²vi - 3uv² - v³i = (u³ - 3uv²) + i*(3u²v - v³)
Então:
(x + i) = (u³ - 3uv²) + i*(3u²v - v³)
e
(x - i) = (u³ - 3uv²) - i*(3u²v - v³)
Logo:
3u²v - v³ = 1
3u² - v² = 1/v

Porém, como u é um inteiro e v também é um inteiro, v só pode ser ±1, caso contrário |1/v| < 1, o que não é uma solução possível para 3u² - v² sendo u e v inteiros.

Assim:
Para v = 1:
3u² - 1 = 1
u² = 3/2
O que não é possível, pois u é inteiro.

Para v = -1
3u² - 1 = -1
u = 0
Ok.

Logo:
(x + i) = (u³ - 3uv²) + i*(3u²v - v³) = 0 + i
Ou seja
x = 0

Neste caso
y³ = 0² + 1
y = 1

Portanto, este exercício só admite uma solução:
x = 0
y = 1


Exercício Resolvido - Potenciação

Um inteiro é chamado formidável se ele pode ser escrito como uma soma de potências distintas de 4 e é dito bem sucedido se ele pode ser escrito como uma soma de duas potências distintas de 6. O número de maneiras de escrevemos 2005 como a soma de um número formidável com um número bem sucedido é: 

a) 0 
b) 1
c) 2
d) 3

e) mais de 3

Solução:

Uma potência de 4 é qualquer número tal que pode ser escrito na forma: 4


Assim, vamos verificar as potências de 4 menores que 2005, isso irá facilitar a resolução do exercício:

4° = 1
4¹ = 4
4² = 16
4³ = 64
4⁴ = 256
4⁵ = 1024

A próxima potência de 4 (4⁶) é maior que 2005, portanto não serve.

Agora escreveremos as potências de 6:
6° = 1
6¹ = 6
6² = 36
6³ = 216
6⁴ = 1296

A próxima potência de 6 (6) é maior que 2005, portanto também não serve.

Agora resta verificar a combinação desses números que resulta em 2005. Porém como 2005 é ímpar, certamente teremos ou 4° = 1 ou 6° = 1 na soma.

É importante perceber que neste exercício temos a liberdade de pegar quantas potências de 4 queremos (desde que sejam distintas), porém as potências de 6 devem ser apenas duas.

Desta forma, pegaremos os maiores valores que são potências de 6 e todos os outros que são potência de 4, desde que a soma não seja superior a 2005.
1296 + 216 + 256 + 64 + 16 + 4 + 1 = 1853.

Desta forma, não existe qualquer combinação destes valores que possam resultar em 2005 pois sob estas condições o maior valor que podemos ter que não passa 2005 é 1853.

Portanto, a resposta correta é a)


Exercícios Resolvido - (UFG 06) - Achar o resto da divisão

(UFG 06) O maior número primo conhecido foi descoberto no ano passado por Martin Nowak. Ele é dado por 225.964.951 –  1. (GALILEU, São Paulo, n. 169, ago. 2005. p. 43). Considerando o algoritmo de Euclides para a divisão por 8 desse número, pode-se escrever a equação 225.964.951 –  1 = 8k + r. Então o resto r da divisão por 8 do maior primo conhecido é:       

a) 0       b) 2       c) 5       d) 6       e) 7

Solução:



Assim:



Substituindo



Como



Logo:



Assim, temos que

.

Letra e)