aritmética

Boa noite, estou bloqueando neste exercício. obrigado pela vossa ajuda
I) a, b, p, q denota números naturais diferentes de zero.
1) suponha que a = 9p + 4q eb = 2p + q. Mostre que PGCD (a, b) = PGCD (p, q)
2) deduzir que 9p + 4 e 2p + 1 são primos entre eles.
3) determinar o GCD dos números naturais 9p + 4 e 2p-1 de acordo com os valores de p
II) mostrar por indução que para cada inteiro natural n diferente de zero,
5 ^ n- (2 ^ n + 3 ^ n) é divisível por 6

para 1) a = 4b + p, portanto, PGCD (a, b) = PGCD (b, p) = PGCD (2p + q, p) mas como continuar dizendo que é = PGCD (p, q)?
2) q = 1 PGCD (9p + 4.2p + q) = PGCD (p, 1) = 1
3) e II) estou completamente seco. Obrigado

Boa noite,

Nós temos as seguintes propriedades:
Para todo x e inteiro diferente de zero, PGCD (x, y) = PGCD (x-y, y)
Para todo x e inteiro diferente de zero, PGCD (x, y) = PGCD (x, y)

Então, você pode concluir do seu raciocínio por 1).

2) está correto do meu ponto de vista.

Para 3) como para II), não tenho idéia neste momento t. II) Eu pareço estar desconectado de I) que não parece lógico, mas hey, pode haver uma maneira de fazer o link.

PGCD (a, b) = PGCD (b, p) = PGCD (2p + q, p) = PGCD (p + q, p) = PGCD (p, q) por isso é bom Obrigado
para II) nosso professor nos disse que ele está desconectado do eu

Ok uma carona

Então, você conhece a noção de congruência?

Poste duplo, na verdade, é mais simples que o esperado com recorrência.

A inicialização é óbvia (colocamos n = 1, e descobrimos que a expressão é 0, que é bem divisível por 0).

Então, assumimos que existe um inteiro n tal que: 6 é dividido 5ⁿ – (2ⁿ3ⁿ)

Vamos mostrar que: 6 divide 5^{n + 1} – (2^{n + 1}3^{n + 1})

1) Como escrever a hipótese: 6 divisões 5ⁿ – (2ⁿ3ⁿ) Retornar à definição de "um inteiro é divisível por outro".

2) Escreva um galit de 5^{n + 1} De acordo com a hipótese de recorrência.

3) Reduza a igualdade para 5.^{n + 1} – (2^{n + 1}3^{n + 1}) Usando recorrência hypostasis.

4) Por meio de uma fatoração bem escolhida, conclui-se que 6 divisões 5^{n + 1} – (2^{n + 1}3^{n + 1})

5) A edição recorrente termina.

Boa sorte e não hesite em fazer suas perguntas!

Ok para 1),

Então você tem uma identidade que pode manipular sem ter que mudar a maior parte da igualdade em si. Portanto, é fácil isolar 5ⁿ para então expressar 5^{n + 1}.

5 ^ (n + 1) = 5 * 5 ^ n = 5 (6k + (2 ^ n) + (3 ^ n)) = 30k + 5 * (2 ^ n) + 5 * (3 ^ n)
30k + 5 * (2 ^ n) + 5 * (3 ^ n) -2 ^ (n + 1) -3 ^ (n + 1) =
30k + 3 * 2 ^ n + 2 * 3 ^ n é bom, então obrigado pela vossa ajuda

mas devo especificar para eu) que não vimos o prop: Para todos os inteiros x, e não zero, PGCD (x, y) = PGCD (x-y, y)
no entanto, acho que devemos usar a propriedade de Euclides em outro momento (se a = bq + r então
PGCD (a, b) = PGCD (b, r)) mas como?

Boa noite,

Níquel para II).

Para a outra questão, PGCD (x, y) = PGCD (x-y, y) é um teste:

Seja d = PGCD (x, y).

Em seguida, divida x e divida y. Existem k e q tais que: x = k * d e y = q * d
De o, ​​d divide x-y porque x-y = d * (k-d) (assumindo que x> e o que nos permite supor que k> d comparando o quociente).

Em seguida, divida o GCD (x-y, y) = D

Por outro lado, D divide x-y e, portanto, existem k & # 39; e q & # 39 ;, de modo que x-y = k & # 39; * D e y = q & # 39; * D
Então: (pela soma das duas equações): x = (k & # 39; + q & # 39;) * D
D: o: D divis xe D se dividem e

Conclusão: D divide o GCD (x, y) = d

Conclusão geral: D = d, que mostra que PGCD (x, y) = PGCD (x-y, y)

E é graças a essa propriedade que se mostra que PGCD (x, y) = PGCD (y, r) quando x = y * q + r.
Precisamente, usamos o fato de que: PGCD (x, y) = PGCD (x-y, y) = … = PGCD (x-q * y, y) = PGCD (r, y)
E PGCD (r, y) = PGCD (y, r) por simetria da função PGCD.

Esperando que tudo isso seja mais claro também.

Boa sorte!

É bom no entanto, temos b = 2p + q, então temos PGCD (b, p) = PGCD (p, q) que dá o resultado diretamente !!
por 3)
Eu mostrei que o GCD dos números naturais 9p + 4 e 2p-1 é 1 ou 17 (este é o valor p)
então eu assumi que PGCD (9p + 4; 2p-1) = 17, então 2p-1 = 17k
o que implica que k é ímpar, então k = 2m + 1
2p-1 = 17 (2m + 1)
2p-1 = 34 m + 17
2p = 34m + 18
p = 17m + 9
mas como é um conjunto, devemos passar por equivalências.
Eu não sei o que adicionar este passo?

Bom Dia,

Quando você chora isso:

Nomeação

temos b = 2p + q então temos PGCD (b, p) = PGCD (p, q)

Você não usa a propriedade:
Se a divisão euclidiana de a por b der igualdade: a = bq + r, então PGCD (a, b) = PGCD (b, r)

mas a propriedade:
Se aeb são dois inteiros tais que a> b, PGCD (a, b) = PGCD (a-b, b)

De fato, na escrita b = 2p + q nada indica que 0 <q <p, o que permitiria afirmar que é a divisão euclidiana de b por p.

Então para 3),

Nomeação

Mostrei que o GCD dos números naturais 9p + 4 e 2p-1 é 1 ou 17

Como
Como teste, chego à mesma conclusão de que você sabe que o GCD parece ser 1 ou 17, mas para provar isso, é necessário proceder por um procedimento empírico, assumindo todos os casos possíveis.

O próximo passo que você dá é bom do meu ponto de vista. Saber que é necessário proceder por análise de síntese. Assume-se que o GCD é 17 e depois encontramos um conjunto de possíveis p.
Então, verificamos que o conjunto encontrado funciona (isto é, que o GCD dá 17).

A dificuldade está em mostrar que se p não pertence ao conjunto em questão, então o GCD é igual a 1.
Uma maneira de fazer isso seria considerar possíveis casos para a forma de p:
p + q = 17k
com q eles vão de 0 a 16 e você tem todos os casos possíveis.
Com um pouco de tempo e cálculo, mostrei que para q = 0, o GCD era bom.
Eu acho que a abordagem é viável, mas um pouco longa, provavelmente há outra maneira de conseguir mais rápido, mas no momento t, eu não tenho isso.

Boa sorte!

Excelente para valores de gcd! Minha abordagem era longa demais para ser viável.
Tendo as possibilidades para o mdc, só resta demonstrar que o que você fez funciona.

Caso contrário, seu professor escolheu uma propriedade intermediária, mas duvido do interesse de tal escolha porque sua demonstração se baseará em um raciocínio semelhante ou mesmo na propriedade minimalista da subtração. Especialmente que esta propriedade é dada em 3 me eles rapidamente dão um extra. Mas tornou-se generalizado sem se limitar ao caso da divisão euclidiana, o que torna possível ter um caso geral incondicional sobre o número inteiro usado.

Grande trabalho