[obm-l] Re: [obm-l] MDC e MMC (sugestões)
Veja na RPM os números 13 29 32 e 51. Vc vai gostar! []’ Hermann From: Vitório Batista Lima da Silva Sent: Monday, April 2, 2018 12:34 PM To: obm-l@mat.puc-rio.br Subject: [obm-l] MDC e MMC (sugestões) Bom dia galera, Estou precisando de dicas sobre material de mdc e mmc para produzir uma sequência didática voltada aos alunos do 6º ano. Grato. Vitório -- Esta mensagem foi verificada pelo sistema de antivírus e acredita-se estar livre de perigo. -- Esta mensagem foi verificada pelo sistema de antiv�rus e acredita-se estar livre de perigo.
[obm-l] Re: [obm-l] MDC e MMC (sugestões)
Pra 6o ano é complicado, pois não dá pra usar álgebra (e, portanto, trabalhar com variáveis que representam números genéricos). Mas, de alguma forma, eu não deixaria de mencionar o algoritmo da divisão com resto: dados dois inteiros positivos a e b (se não me engano, alunos de 6o ano ainda não viram números negativos), existem inteiros positivos q e r, com 0 <= r < b, tais que a = qb + r. Pois este algoritmo está na base do algoritmo euclidiano pra achar o mdc de dois números (e, de fato, na base de toda a teoria dos números). Os livros de EF que eu vi usam (mas não demonstram) um algoritmo pra calcular mmc que só funciona bem quando os números só têm fatores primos pequenos e fáceis de achar. Algo assim: pra calcular mmc(168,126): 168, 126 | 2 84,63 | 3 28,21 | 7 4, 3 | primos entre si Logo, mmc(168,126) = 2*3*7*4*3 = 2^3 * 3^2 * 7 = 504 Mas tente usar isso pra calcular mmc(7957,7081)... Já pelo algoritmo Euclidiano: 7957 = 1*7081 + 876 7081 = 8*876 + 73 876 = 12*73 ==> mdc(7957,7081) = 73 ==> mmc(7957,7081) = 7957*7081/73 = 771829. Uma sugestão (mas que pode ser muito trabalhosa) é pegar um bom livro de teoria elementar dos números e adaptar o primeiro capítulo (que normalmente trata dessas coisas) pro nível de 6o ano. Isso provavelmente significa substituir as demonstrações algébricas por exemplos de casos particulares que exibem todas as características do caso geral. A ideia certamente não é demonstrar rigorosamente qualquer teorema. Mas acho que, usando bons exemplos, dá pra explicar pros alunos porque os resultados são verdadeiros e porque os algoritmos funcionam. Me parece importante que eles entendam isso e não se limitem a memorizar mais uma receita de bolo. Outra coisa que me parece interessante é encorajar os alunos a usarem planilhas pra gerar conjecturas e implementar algoritmos. Acho que esta atividade vai ajudá-los a fixar a teoria e também pode ser uma bela introdução à álgebra. Aliás, adquirir proficiência no uso de planilhas (habilidade importante em qualquer profissão) me parece ser um dos melhores argumentos pra se estudar álgebra na escola. []s, Claudio. 2018-04-02 12:34 GMT-03:00 Vitório Batista Lima da Silva < vitorio.si...@trf1.jus.br>: > Bom dia galera, > > > > Estou precisando de dicas sobre material de mdc e mmc para produzir uma > sequência didática voltada aos alunos do 6º ano. > > > > Grato. > > > > Vitório > > > > > > > > > > -- > Esta mensagem foi verificada pelo sistema de antivírus e > acredita-se estar livre de perigo. > -- Esta mensagem foi verificada pelo sistema de antiv�rus e acredita-se estar livre de perigo.
Re: [obm-l] mdc(a^n - 1, a^m - 1) = a^d - 1
oi Em 08/07/14, Artur Costa Steinersteinerar...@gmail.com escreveu: De nada! Podemos concluir de bate pronto que, dentre os divisores comuns de a^m - 1 e a^n - 1 que sejam da forma a^r - 1, o maior é a^d - 1. Mas não sei pode haver um divisor comum a^ d - 1 que não seja da forma a^r - 1. Vou analisar mais. Artur Costa Steiner Em 08/07/2014, às 09:04, Pedro Chaves brped...@hotmail.com escreveu: Muito obrigado, caro Artur, pela demonstração do teorema abaixo: Teorema: Sendo a, n e m inteiros positivos, com a 1, a^n - 1 divide a^m - 1 se, e somente se, n divide m. Bem... usando-se esse teorema, seria possível demonstrar que o mdc(a^n- 1, a^m - 1)= a^d - 1, sendo d = mdc(m, n)? Abraços do pedro Chaves! ___ -- Esta mensagem foi verificada pelo sistema de antivírus e acredita-se estar livre de perigo. = Instruções para entrar na lista, sair da lista e usar a lista em http://www.mat.puc-rio.br/~obmlistas/obm-l.html = -- Esta mensagem foi verificada pelo sistema de antivírus e acredita-se estar livre de perigo. = Instru�ões para entrar na lista, sair da lista e usar a lista em http://www.mat.puc-rio.br/~obmlistas/obm-l.html = -- Esta mensagem foi verificada pelo sistema de antiv�rus e acredita-se estar livre de perigo. = Instru��es para entrar na lista, sair da lista e usar a lista em http://www.mat.puc-rio.br/~obmlistas/obm-l.html =
Re: [obm-l] mdc(a^n - 1, a^m - 1) = a^d - 1
Hmmm Eu acho que o seguinte eh verdadeiro: Lema: Considere a seguinte iteracao: dado o conjunto {x,y} com xy0, troque-o por {x,x-y}. Eu afirmo que voce pode repetir esta iteracao ateh ficar com o conjunto unitario {d} onde d=mdc{x_original, y_original}. Dem.: Pense como funciona o algoritmo para encontrar m.d.c., mas ao inves de dividir x por y para achar x=qy+d, subtraia y de x (q vezes) ateh ficar com d. Agora, supondo nm, qualquer divisor comum de a^n-1 e a^m-1 tem que dividir a diferenca (a^n-a^m)=a^m (a^(n-m)-1), supondo nm. Como a^m eh primo com a^m-1, concluo que ele tem que ser divisor de a^(n-m)-1. Alias, VAI E VOLTA: supondo nm, b eh divisor comum de a^n-1 e a^m-1 SE, E SOMENTE SE, b eh divisor comum de a^m-1 e a^(n-m)-1. Ou seja, os divisores comuns dessas expressoes nao mudam ao perfazer a operacao de trocar {m,n} por {m,n-m}. Itere esta ideia e voce vai chegar que b tem que ser divisor de a^d-1 onde d=mdc{m,n}. Entao nao ha nada maior mesmo. Abraco, Ralph 2014-07-09 14:42 GMT-03:00 Arthur Max wm4x@gmail.com: oi Em 08/07/14, Artur Costa Steinersteinerar...@gmail.com escreveu: De nada! Podemos concluir de bate pronto que, dentre os divisores comuns de a^m - 1 e a^n - 1 que sejam da forma a^r - 1, o maior 茅 a^d - 1. Mas n茫o sei pode haver um divisor comum a^ d - 1 que n茫o seja da forma a^r - 1. Vou analisar mais. Artur Costa Steiner Em 08/07/2014, 脿s 09:04, Pedro Chaves brped...@hotmail.com escreveu: Muito obrigado, caro Artur, pela demonstra莽茫o do teorema abaixo: Teorema: Sendo a, n e m inteiros positivos, com a 1, a^n - 1 divide a^m - 1 se, e somente se, n divide m. Bem... usando-se esse teorema, seria poss铆vel demonstrar que o mdc(a^n- 1, a^m - 1)= a^d - 1, sendo d = mdc(m, n)? Abra莽os do pedro Chaves! ___ -- Esta mensagem foi verificada pelo sistema de antiv铆rus e acredita-se estar livre de perigo. = Instru莽玫es para entrar na lista, sair da lista e usar a lista em http://www.mat.puc-rio.br/~obmlistas/obm-l.html = -- Esta mensagem foi verificada pelo sistema de antiv铆rus e acredita-se estar livre de perigo. = Instru锟矫礶s para entrar na lista, sair da lista e usar a lista em http://www.mat.puc-rio.br/~obmlistas/obm-l.html = -- Esta mensagem foi verificada pelo sistema de antiv韗us e acredita-se estar livre de perigo. = Instru珲es para entrar na lista, sair da lista e usar a lista em http://www.mat.puc-rio.br/~obmlistas/obm-l.html = -- Esta mensagem foi verificada pelo sistema de antiv�rus e acredita-se estar livre de perigo. = Instru��es para entrar na lista, sair da lista e usar a lista em http://www.mat.puc-rio.br/~obmlistas/obm-l.html =
Re: [obm-l] mdc(a^n - 1, a^m - 1) = a^d - 1
Desculpa pela mensagem errada pessoal, foi um amigo da faculdade quando deixei meu e-mail aberto no lab. []'s Em 09/07/14, Ralph Teixeiraralp...@gmail.com escreveu: Hmmm Eu acho que o seguinte eh verdadeiro: Lema: Considere a seguinte iteracao: dado o conjunto {x,y} com xy0, troque-o por {x,x-y}. Eu afirmo que voce pode repetir esta iteracao ateh ficar com o conjunto unitario {d} onde d=mdc{x_original, y_original}. Dem.: Pense como funciona o algoritmo para encontrar m.d.c., mas ao inves de dividir x por y para achar x=qy+d, subtraia y de x (q vezes) ateh ficar com d. Agora, supondo nm, qualquer divisor comum de a^n-1 e a^m-1 tem que dividir a diferenca (a^n-a^m)=a^m (a^(n-m)-1), supondo nm. Como a^m eh primo com a^m-1, concluo que ele tem que ser divisor de a^(n-m)-1. Alias, VAI E VOLTA: supondo nm, b eh divisor comum de a^n-1 e a^m-1 SE, E SOMENTE SE, b eh divisor comum de a^m-1 e a^(n-m)-1. Ou seja, os divisores comuns dessas expressoes nao mudam ao perfazer a operacao de trocar {m,n} por {m,n-m}. Itere esta ideia e voce vai chegar que b tem que ser divisor de a^d-1 onde d=mdc{m,n}. Entao nao ha nada maior mesmo. Abraco, Ralph 2014-07-09 14:42 GMT-03:00 Arthur Max wm4x@gmail.com: oi Em 08/07/14, Artur Costa Steinersteinerar...@gmail.com escreveu: De nada! Podemos concluir de bate pronto que, dentre os divisores comuns de a^m - 1 e a^n - 1 que sejam da forma a^r - 1, o maior 茅 a^d - 1. Mas n茫o sei pode haver um divisor comum a^ d - 1 que n茫o seja da forma a^r - 1. Vou analisar mais. Artur Costa Steiner Em 08/07/2014, 脿s 09:04, Pedro Chaves brped...@hotmail.com escreveu: Muito obrigado, caro Artur, pela demonstra莽茫o do teorema abaixo: Teorema: Sendo a, n e m inteiros positivos, com a 1, a^n - 1 divide a^m - 1 se, e somente se, n divide m. Bem... usando-se esse teorema, seria poss铆vel demonstrar que o mdc(a^n- 1, a^m - 1)= a^d - 1, sendo d = mdc(m, n)? Abra莽os do pedro Chaves! ___ -- Esta mensagem foi verificada pelo sistema de antiv铆rus e acredita-se estar livre de perigo. = Instru莽玫es para entrar na lista, sair da lista e usar a lista em http://www.mat.puc-rio.br/~obmlistas/obm-l.html = -- Esta mensagem foi verificada pelo sistema de antiv铆rus e acredita-se estar livre de perigo. = Instru锟矫礶s para entrar na lista, sair da lista e usar a lista em http://www.mat.puc-rio.br/~obmlistas/obm-l.html = -- Esta mensagem foi verificada pelo sistema de antiv韗us e acredita-se estar livre de perigo. = Instru珲es para entrar na lista, sair da lista e usar a lista em http://www.mat.puc-rio.br/~obmlistas/obm-l.html = -- Esta mensagem foi verificada pelo sistema de antivírus e acredita-se estar livre de perigo. = Instru�ões para entrar na lista, sair da lista e usar a lista em http://www.mat.puc-rio.br/~obmlistas/obm-l.html = -- Esta mensagem foi verificada pelo sistema de antiv�rus e acredita-se estar livre de perigo. = Instru��es para entrar na lista, sair da lista e usar a lista em http://www.mat.puc-rio.br/~obmlistas/obm-l.html =
Re: [obm-l] mdc(a^n - 1, a^m - 1) = a^d - 1
De nada! Podemos concluir de bate pronto que, dentre os divisores comuns de a^m - 1 e a^n - 1 que sejam da forma a^r - 1, o maior é a^d - 1. Mas não sei pode haver um divisor comum a^ d - 1 que não seja da forma a^r - 1. Vou analisar mais. Artur Costa Steiner Em 08/07/2014, às 09:04, Pedro Chaves brped...@hotmail.com escreveu: Muito obrigado, caro Artur, pela demonstração do teorema abaixo: Teorema: Sendo a, n e m inteiros positivos, com a 1, a^n - 1 divide a^m - 1 se, e somente se, n divide m. Bem... usando-se esse teorema, seria possível demonstrar que o mdc(a^n- 1, a^m - 1)= a^d - 1, sendo d = mdc(m, n)? Abraços do pedro Chaves! ___ -- Esta mensagem foi verificada pelo sistema de antivírus e acredita-se estar livre de perigo. = Instruções para entrar na lista, sair da lista e usar a lista em http://www.mat.puc-rio.br/~obmlistas/obm-l.html = -- Esta mensagem foi verificada pelo sistema de antiv�rus e acredita-se estar livre de perigo. = Instru��es para entrar na lista, sair da lista e usar a lista em http://www.mat.puc-rio.br/~obmlistas/obm-l.html =
[obm-l] Re: [obm-l] mdc e mmc de frações
Eu nunca ouvi falar em mdc e mmc de não inteiros. Em 23 de junho de 2014 22:18, Pedro Chaves brped...@hotmail.com escreveu: Caros colegas, Como obter o máximo divisor comum e o menor múltiplo comum de duas frações quaisquer cujos termos são inteiros positivos? Por exemplo: Calcular o mdc e o mmc das frações 6/5 e 4/9. Desde já, muito obrigado. Pedro Chaves -- Esta mensagem foi verificada pelo sistema de antivírus e acredita-se estar livre de perigo. = Instruções para entrar na lista, sair da lista e usar a lista em http://www.mat.puc-rio.br/~obmlistas/obm-l.html = -- Cássio Anderson Graduando em Matemática - UFPB -- Esta mensagem foi verificada pelo sistema de antiv�rus e acredita-se estar livre de perigo.
Re: [obm-l] MDC
Sim, sim obrigado! Em 28 de setembro de 2013 21:47, terence thirteen peterdirich...@gmail.comescreveu: Em 28 de setembro de 2013 15:56, Pedro Júnior pedromatematic...@gmail.com escreveu: Como mostro que mdc(an,bn)=n. mdc(a,b). A proposição é claríssima, mas não estou conseguindo concluir. Vamos pelo velho método indígena: fatoração! Por demonstração, o MDC de dois caras consiste no produto de todos os primos comuns a ambos os termos, cada um deles com o menor expoente que estiver presente entre ambos. Por exemplo, MDC (2^3*3^2, 2^5*5^1) = 2^3 Assim sendo, vamos pegar um primo p. este primo aparece A vezes em a, B vezes em b, N vezes em n. Então, ele aparecerá A+N vezes em an, B+N vezes em bn, e portanto aparecerá MAX(A+N,B+N) vezes em MDC(an,bn) Igualmente, ele aparecerá A vezes em a, B vezes em b, e portanto aparecerá N+MAX(A,B) vezes em n*MDC(a,b) Assim, basta demonstrar que MAX(A+N,B+N) = N+MAX(A,B). Me parece mais fácil, não? :P Uma dica para o futuro: as funções MDC e MMC são duais a MAX e MIN. -- Pedro Jerônimo S. de O. Júnior Geo João Pessoa – PB -- Esta mensagem foi verificada pelo sistema de antivírus e acredita-se estar livre de perigo. -- /**/ 神が祝福 Torres -- Esta mensagem foi verificada pelo sistema de antivírus e acredita-se estar livre de perigo. -- Pedro Jerônimo S. de O. Júnior Professor de Matemática Geo João Pessoa – PB -- Esta mensagem foi verificada pelo sistema de antiv�rus e acredita-se estar livre de perigo.
Re: [obm-l] MDC
Em 28 de setembro de 2013 15:56, Pedro Júnior pedromatematic...@gmail.comescreveu: Como mostro que mdc(an,bn)=n. mdc(a,b). A proposição é claríssima, mas não estou conseguindo concluir. Vamos pelo velho método indígena: fatoração! Por demonstração, o MDC de dois caras consiste no produto de todos os primos comuns a ambos os termos, cada um deles com o menor expoente que estiver presente entre ambos. Por exemplo, MDC (2^3*3^2, 2^5*5^1) = 2^3 Assim sendo, vamos pegar um primo p. este primo aparece A vezes em a, B vezes em b, N vezes em n. Então, ele aparecerá A+N vezes em an, B+N vezes em bn, e portanto aparecerá MAX(A+N,B+N) vezes em MDC(an,bn) Igualmente, ele aparecerá A vezes em a, B vezes em b, e portanto aparecerá N+MAX(A,B) vezes em n*MDC(a,b) Assim, basta demonstrar que MAX(A+N,B+N) = N+MAX(A,B). Me parece mais fácil, não? :P Uma dica para o futuro: as funções MDC e MMC são duais a MAX e MIN. -- Pedro Jerônimo S. de O. Júnior Geo João Pessoa – PB -- Esta mensagem foi verificada pelo sistema de antivírus e acredita-se estar livre de perigo. -- /**/ 神が祝福 Torres -- Esta mensagem foi verificada pelo sistema de antiv�rus e acredita-se estar livre de perigo.
Re: [obm-l] mdc como combinação linear
Ennius, Veja o artigo Divisibilidade, congruências e aritmética módulo n na revista Eureka número 2. A demonstração que vc quer está logo no início, mas o artigo todo é muito bom. Abç, Renato Madeira. Em 13/01/2013, às 09:35, ennius enn...@bol.com.br escreveu: Colegas da lista, Como podemos demonstrar que o mdc de dois ou mais números inteiros (não todos nulos) pode ser representado como combinação linear (usando-se somente inteiros) desses números? Desde já, muito obrigado. Ennius Lima __ = Instru��es para entrar na lista, sair da lista e usar a lista em http://www.mat.puc-rio.br/~obmlistas/obm-l.html = = Instru��es para entrar na lista, sair da lista e usar a lista em http://www.mat.puc-rio.br/~obmlistas/obm-l.html =
Re: [obm-l] mdc de números ímpares (pares) consecutivos
Olá a todos. Peço licença para esboçar uma tentativa de solução, não sei se o modo de descrição está bom, mas gostaria de compartilhar esta ideia. Inclusive de saber como melhorar na escrita da resposta. Seria algo assim: pares: m,n com m=2x e n=2x+2 mdc(m,n) = mdc (2x,2x+2) = 2*mdc(x,x+1) Pelo Teorema Fundamental da Aritmética, o mdc de x e x+1 é 1, já que os primos de x não são os mesmos de x+1. ímpares: m,n com m=2x+1 e n=2x+3 mdc(m,n) = mdc (2x+1,2x+3) Dividindo (subtraindo) o maior pelo menor, fica: 2x+3-2x-1 = 2 e como mdc (a,b) = mdc (b,a-b) para ab fica: mdc(m,n) = mdc (2x+1,2x+3) = mdc (2x+1,2) = 1 já que 2x+1 é ímpar e 2 é par. []'s Em Mon, 31 Dec 2012 16:28:35 -0200 ennius enn...@bol.com.br escreveu: Caros Amigos , Como poderemos provar as duas afirmações abaixo? 1) O mdc de dois números Ãmpares consecutivos é 1. 2) O mdc de dois números pares consecutivos é 2. Abraços do Ennius Lima! ___ = Instruções para entrar na lista, sair da lista e usar a lista em http://www.mat.puc-rio.br/~obmlistas/obm-l.html = = Instru��es para entrar na lista, sair da lista e usar a lista em http://www.mat.puc-rio.br/~obmlistas/obm-l.html =
RE: [obm-l] MDC
Se as 2 escadas vão até o último andar e cada andar tem o mesmo número de degraus, Teríamos que achar um número K que é tanto múltiplo de 800 como de 1000, mas tal que 800/K e 1000/K são primos entre siTrata-se do mdc entre 800 e 100, e o prédio tem 200 andares Realmente 4 degraus por andar é meio difícil de se ter, mas não deixa de ser a resposta []'sJoão From: mat.mo...@gmail.com Date: Fri, 30 Sep 2011 06:10:55 -0300 Subject: [obm-l] MDC To: obm-l@mat.puc-rio.br Estou tentando resolver esse problema, o qual não estou convicto da solução aparente. Encontra-se num capítulo de algorítimo de Euclides. Um prédio possui duas escadarias, uma delas com 1000 degraus e outra com 800 degraus. Sabendo que os degraus das duas escadas só estão no mesmo nível quando conduzem a um andar, descubra quantos andares tem o prédio. Fiz o que era óbivio: mdc(800,1000) = 200, mas seria essa a interpretação, 200 andares, uma escada muda de andar de 4 em 4 degraus e a outra de 5 em 5? Se foir é muito incoerentre. Agradeceria uma opinião, orientação. Obrigado.
[obm-l] Re: [obm-l] mdc (a^x – 1, a^y – 1, a^z – 1, .. .......) = [a^mdc(x, y, z,...)] – 1
Para dois caras, é fácil demonstrar na raça, usando Euclides: MDC(a^x-1,a^y-1)= MDC(a^x-1,a^(x-y)-1). Daí se faz por indução no número de variáveis. Em 23/11/10, Paulo Argolopauloarg...@bol.com.br escreveu: Caros Colegas, Estou refazendo o enunciado da questão. Como provar o teorema seguinte sobre máximo divisor comum? TEOREMA: O máximo divisor comum (mdc) dos números do tipo a^x -1 , onde a e x são números inteiros maiores do que 1, é dado pela expressão abaixo: mdc(a^x - 1, a^y - 1, a^z - 1, ... ) = [a^mdc(x, y, z,...)] -1 Grato, Paulo Argolo = Instru�ões para entrar na lista, sair da lista e usar a lista em http://www.mat.puc-rio.br/~obmlistas/obm-l.html = -- /**/ Quadrinista e Taverneiro! http://tavernadofimdomundo.blogspot.com Quadrinhos, histórioas e afins http://baratoeletrico.blogspot.com / Um pouco sobre elétrons em movimento http://bridget-torres.blogspot.com/ Personal! Do not edit! = Instru��es para entrar na lista, sair da lista e usar a lista em http://www.mat.puc-rio.br/~obmlistas/obm-l.html =
[obm-l] Re: [obm-l] mdc(bbb...b, bbb...b) é bbb...b
Olá Paulo, Considere genericamente uma base q. Se X = bbb...b e Y = bbb...bbb nessa base, então X = b*(1 + q + ... + q^(a*d-1)) e Y = b*(1 + q + ... + q^(m*d-1)), onde n = a*d, k = m*d e o d = mdc(n,k). Note também que X = b*[(q^d - 1)/(q - 1)]*[(Q^a - 1)/(Q - 1)] e Y = b*[(q^d - 1)/(q - 1)]*[(Q^m - 1)/(Q - 1)], onde Q = q^d. Isso mostra que v = b*[(q^d - 1)/(q - 1)] = b*(1 + q + ... + q^(d-1)) é divisor comum de X e Y. Resta mostrar que é máximo. Para tanto, basta verificar que se p é primo e divide W = [(Q^a - 1)/(Q - 1)] e Z = [(Q^m - 1)/(Q - 1)], então p divide 1, absurdo, donde p não existe e mdc (Z,W) = 1. Em outras palavras, v será o mdc de X e Y. Suponhamos, sem perda de generalidade, que W Z, ou seja, a m. p | Z = 1 + Q + ... + Q^(a-1) p | W = 1 + Q + ... + Q^(m-1) Logo, p | (Z - W) = Q^m*(1 + Q + ... + Q^(a - m - 1)). É fácil ver que p não pode dividir Q, do contrário, de p | Z teríamos que p | 1. Assim, p | (1 + Q + ... + Q^(a - m - 1)). Existe um natural s mínimo tal que m a - s*m 0. Ao repetir o processo acima trocando a por a - m, e depois por a - 2*m, e assim por diante, obteremos indutivamente, para vários r, que p | 1 + Q + ... + Q^(a - (r+1)*m - 1). Esse processo não pode ser aplicado indefinidamente! Só vale até chegarmos a s-1, gerando implicações sobre s. Em particular, p | 1 + Q + ... + Q^(a - s*m - 1), com c_0 = m a - s*m = c_1 0. Repetindo o processo, agora trocando c_0 por c_1, e assim sucessivamente, obteremos uma seqüência decrescente de naturais c_t tais que p | 1 + Q + ... + Q^(c_t - 1). Ora, por sua natureza decrescente, inteira e positiva, em algum momento o processo termina, com c_t = 1. Isso implica que não teremos saída, e necessariamente p | 1, absurdo. Isso demonstra que v = b*[(q^d - 1)/(q - 1)] = b*(1 + q + ... + q^(d-1)) é o mdc de X e Y. Abraços, Daniel Em 16 de novembro de 2010 22:06, Paulo Argolo pauloarg...@bol.com.brescreveu: Caros Colegas, Como podemos provar o teorema abaixo: O máximo divisor comum dos números naturais bbb...b (n dígitos iguais a b) e bbb...n (k dígitos iguais a b) é bbb...b (d dígitos iguais a b), d é o máximo divisor comum de n e k. Abraços! Paulo = Instru�ões para entrar na lista, sair da lista e usar a lista em http://www.mat.puc-rio.br/~obmlistas/obm-l.html=
Re: [obm-l] mdc
Um exemplinho pra te dar uma idéia do que se pode fazer nesta questão: mdc(65,75) 75/65 = 1, resto 10 65/10 = 6, resto 5 10/5 = 2, resto 0 = o MDC é 5, os quocientes são 2, 6, 1. Note que o último quociente nunca pode ser 1 (os números nunca são iguais. Prove isso! - para você mesmo), mas todos os outros podem. Agora, é mais uma questão de fazer o processo inverso do algoritmo de Euclides (ou divisões sucessivas) sabendo quais são os quocientes e voltando no tempo. A única coisa chata com este algoritmo é que as opiniões divergem quanto à última divisão ser considerada uma das etapas ou não (para fazer 3). Eu acho que sim, neste problema pelo menos, porque senão é impossível saber qual é a última divisão que foi feita. Quanto à explicação, acho que o melhor a fazer neste caso é primeiro resolver alguns MDCs pelo método, mostrar para o aluno, e ver que ele é capaz de reconstruir as etapas, assim como ele é capaz de fazer + 34 = 56 + 56 = 98 e assim por diante. Um grande abraço, -- Bernardo Freitas Paulo da Costa 2009/9/16 Silas Gruta silasgr...@gmail.com: Olá Colegas Um aluno do 5° ano me trouxe esse exercício de MDC do colégio militar e passei a maior vergonha por não conseguir resolvê-lo. Preciso explicar de forma que um menino de 10 anos entenda. Poderiam dar uma mãozinha a este colega que tem MUUITO a aprender ainda? O mdc de dois números determinado pelo processo das divisões sucessivas é 396. Havendo três quocientes que são os menores possíveis, determine o maior dos dois números obrigado pela ajuda! -- Silas Gruta = Instruções para entrar na lista, sair da lista e usar a lista em http://www.mat.puc-rio.br/~obmlistas/obm-l.html =
Re: [obm-l] mdc
Bom, se os quocientes são os menores possíveis então são 1, 1 e 2 então 1 1 2 AB C 396 C 396 0 Bom esse é o esquema das divisões sucessivas, faltam as linhas que não consigo desenhar. Então C = 2x396+0 = 792 B= 1x C + 396 = 1188 A = 1xB + C = 1188 + 792 = 1980 . 2009/9/16 Bernardo Freitas Paulo da Costa bernardo...@gmail.com Um exemplinho pra te dar uma idéia do que se pode fazer nesta questão: mdc(65,75) 75/65 = 1, resto 10 65/10 = 6, resto 5 10/5 = 2, resto 0 = o MDC é 5, os quocientes são 2, 6, 1. Note que o último quociente nunca pode ser 1 (os números nunca são iguais. Prove isso! - para você mesmo), mas todos os outros podem. Agora, é mais uma questão de fazer o processo inverso do algoritmo de Euclides (ou divisões sucessivas) sabendo quais são os quocientes e voltando no tempo. A única coisa chata com este algoritmo é que as opiniões divergem quanto à última divisão ser considerada uma das etapas ou não (para fazer 3). Eu acho que sim, neste problema pelo menos, porque senão é impossível saber qual é a última divisão que foi feita. Quanto à explicação, acho que o melhor a fazer neste caso é primeiro resolver alguns MDCs pelo método, mostrar para o aluno, e ver que ele é capaz de reconstruir as etapas, assim como ele é capaz de fazer + 34 = 56 + 56 = 98 e assim por diante. Um grande abraço, -- Bernardo Freitas Paulo da Costa 2009/9/16 Silas Gruta silasgr...@gmail.com: Olá Colegas Um aluno do 5° ano me trouxe esse exercício de MDC do colégio militar e passei a maior vergonha por não conseguir resolvê-lo. Preciso explicar de forma que um menino de 10 anos entenda. Poderiam dar uma mãozinha a este colega que tem MUUITO a aprender ainda? O mdc de dois números determinado pelo processo das divisões sucessivas é 396. Havendo três quocientes que são os menores possíveis, determine o maior dos dois números obrigado pela ajuda! -- Silas Gruta = Instruções para entrar na lista, sair da lista e usar a lista em http://www.mat.puc-rio.br/~obmlistas/obm-l.html =
Re: [obm-l] mdc
Uma coisa interessante é que no cálculo do MDC de 2 números sempre o último menor quociente será 2. 2009/9/16 JOSE AIRTON CARNEIRO nep...@ig.com.br: Bom, se os quocientes são os menores possíveis então são 1, 1 e 2 então 1 1 2 A B C 396 C 396 0 Bom esse é o esquema das divisões sucessivas, faltam as linhas que não consigo desenhar. Então C = 2x396+0 = 792 B= 1x C + 396 = 1188 A = 1xB + C = 1188 + 792 = 1980 . 2009/9/16 Bernardo Freitas Paulo da Costa bernardo...@gmail.com Um exemplinho pra te dar uma idéia do que se pode fazer nesta questão: mdc(65,75) 75/65 = 1, resto 10 65/10 = 6, resto 5 10/5 = 2, resto 0 = o MDC é 5, os quocientes são 2, 6, 1. Note que o último quociente nunca pode ser 1 (os números nunca são iguais. Prove isso! - para você mesmo), mas todos os outros podem. Agora, é mais uma questão de fazer o processo inverso do algoritmo de Euclides (ou divisões sucessivas) sabendo quais são os quocientes e voltando no tempo. A única coisa chata com este algoritmo é que as opiniões divergem quanto à última divisão ser considerada uma das etapas ou não (para fazer 3). Eu acho que sim, neste problema pelo menos, porque senão é impossível saber qual é a última divisão que foi feita. Quanto à explicação, acho que o melhor a fazer neste caso é primeiro resolver alguns MDCs pelo método, mostrar para o aluno, e ver que ele é capaz de reconstruir as etapas, assim como ele é capaz de fazer + 34 = 56 + 56 = 98 e assim por diante. Um grande abraço, -- Bernardo Freitas Paulo da Costa 2009/9/16 Silas Gruta silasgr...@gmail.com: Olá Colegas Um aluno do 5° ano me trouxe esse exercício de MDC do colégio militar e passei a maior vergonha por não conseguir resolvê-lo. Preciso explicar de forma que um menino de 10 anos entenda. Poderiam dar uma mãozinha a este colega que tem MUUITO a aprender ainda? O mdc de dois números determinado pelo processo das divisões sucessivas é 396. Havendo três quocientes que são os menores possíveis, determine o maior dos dois números obrigado pela ajuda! -- Silas Gruta = Instruções para entrar na lista, sair da lista e usar a lista em http://www.mat.puc-rio.br/~obmlistas/obm-l.html = = Instru��es para entrar na lista, sair da lista e usar a lista em http://www.mat.puc-rio.br/~obmlistas/obm-l.html =
Re: [obm-l] mdc
A idéia é exatamente esso, mas tem um detalhe sórdido : como você mesmo mostrou, o mdc tem que dividir 3ab e (a+b) ao mesmo tempo (já que se ele divide a+b ele vai dividir também o resto, que é (a+b)^2). Se a+b for múltiplo de 3, então o mdc é *no mínimo* 3. O que faltou foi ver que não pode ser maior do que isso, e é aí que entra a parte de a e b são primos entre si. Vejamos : se o mdc tiver algum outro fator, m por exemplo, como ele divide 3ab (é ótimo ter uma parcela fatorada pra calcular mdcs!) ele divide 3, a, ou b (não necessariamente exclusivo). Bom, como o 3 já foi contado, ele divide a ou b. Podemos supor que divide a (o outro caso é simétrico!). Como é mdc, ele divide também, a+b. Como m divide a e m divide a+b, m divide (a+b) - a = b (esse truque é ótimo, e ajuda a simplificar as contas, e foi bem o que o Saulo fez). Mas daí m divide a e b, e como eles são primos entre si, m = 1. A gente provou então que se tem um fator que divide 3ab e a+b ao mesmo tempo, ele não divide nem a nem b. Então, ele divide 3, e é 1 ou 3. Daí, a gente prova uma coisa um tiquinho mais forte : o mdc é 3 se e somente se a+b é múltiplo de 3 ! Abraços, -- Bernardo Freitas Paulo da Costa 2008/3/27 saulo nilson [EMAIL PROTECTED]: (a^2+b^2-ab)/(a+b)=((a+b)^2-3ab)/(a+b) o maximo divisor comum e o maior numero que nos podemos por em evidencia no numerador e no denominador da divisao acima. a+b=pode ser multiplo 3 entao mdc(a+b,a²-ab+b²) =1 ou 3 2008/3/27 Eder Albuquerque [EMAIL PROTECTED]: Pessoal, o problema a seguir caiu numa prova de teoria dos números que fiz ontem e foi a única dúvida... Provar: mdc(a,b)= 1 = mdc(a+b,a²-ab+b²) =1 ou 3 Agradeço se alguém mostrar como se prova. Eder Abra sua conta no Yahoo! Mail, o único sem limite de espaço para armazenamento! = Instruções para entrar na lista, sair da lista e usar a lista em http://www.mat.puc-rio.br/~obmlistas/obm-l.html =
Re: [obm-l] mdc
(a^2+b^2-ab)/(a+b)=((a+b)^2-3ab)/(a+b) o maximo divisor comum e o maior numero que nos podemos por em evidencia no numerador e no denominador da divisao acima. a+b=pode ser multiplo 3 entao mdc(a+b,a²-ab+b²) =1 ou 3 2008/3/27 Eder Albuquerque [EMAIL PROTECTED]: Pessoal, o problema a seguir caiu numa prova de teoria dos números que fiz ontem e foi a única dúvida... Provar: mdc(a,b)= 1 = mdc(a+b,a²-ab+b²) =1 ou 3 Agradeço se alguém mostrar como se prova. Eder -- Abra sua conta no Yahoo! Mailhttp://br.rd.yahoo.com/mail/taglines/mail/*http://br.mail.yahoo.com/, o único sem limite de espaço para armazenamento!
Re:[obm-l] mdc
Bom se x é inteiro, posso expressá-lo como x=p(1)^k (1).p(2)^k(2). ... .p(n)^k(n) pelo T. fat. única. onde p(i) denota um certo número primo e k(i) denota um natural, com i pertencente ao cjto. {1,2,...,n) 1 é divisível somente pelos inteiros -1 e +1 Logo seu maior divisor é o número 1. x pode ser um número composto ou um primo. Em qualquer um dos casos, teremos que x=x.1 pois no corpo dos números inteiros 1 é o elemento neutro em relação à adição. Assim parece-me trivial pois x e 1 tem 1 e -1 como divisores comuns, portanto o maior divisor comum entre eles é certamento o número 1. Além disso você pode utilizar esse fato aqui: xe y são inteiros O mdc entre x e x-1 é 1 logo pelas props. do mdc temos que mdc(a,a-1)=1=mdc(a,a-1-(a))=mdc(a,-1)=mdc(a,1) Gostaria de saber como defino a noção de MDC em Z[x] e como provo que MDC{x,1} = 1. Gostaria de saber também mais duas coisas: i) como defininir a noção de irredutibilidade em um domínio D; ii) usando o teorema da fatoração única (para polinômios), como posso definir o MMC de polinômios. Obs.: Z = {números inteiros} Grato desde já com a possível ajuda de vocês. - Yahoo! Messenger - Fale com seus amigos online. Instale agora! Atenciosamente, Engenharia Elétrica - UNESP Ilha Solteira Osvaldo Mello Sponquiado Usuário de GNU/Linux __ Acabe com aquelas janelinhas que pulam na sua tela. AntiPop-up UOL - É grátis! http://antipopup.uol.com.br/ = Instruções para entrar na lista, sair da lista e usar a lista em http://www.mat.puc-rio.br/~nicolau/olimp/obm-l.html =
Re:[obm-l] mdc
Meu caro Osvaldo, sua resposta estaria correta se x fosse um número inteiro, mas x é um polinômio em Z[x] = {polinômios com coefientes em Z}.Osvaldo [EMAIL PROTECTED] wrote: Bom se x é inteiro, posso expressá-lo como x=p(1)^k(1).p(2)^k(2). ... .p(n)^k(n) pelo T. fat. única.onde p(i) denota um certo número primo e k(i) denota um natural, com i pertencente ao cjto. {1,2,...,n)1 é divisível somente pelos inteiros -1 e +1 Logo seu maior divisor é o número 1.x pode ser um número composto ou um primo. Em qualquer um dos casos, teremos que x=x.1 pois no corpo dos números inteiros 1 é o elemento neutro em relação à adição.Assim parece-me trivial pois x e 1 tem 1 e -1 como divisores comuns, portanto o maior divisor comum entre eles é certamento o número 1.Além disso você pode utilizar esse fato aqui:xe y são inteirosO mdc entre x e x-1 é 1 logo pelas props. do mdc temos que mdc(a,a-1)=1=mdc(a,a-1-(a))=mdc(a,-1)=mdc(a,1) Gostaria de saber como defino a noção de MDC em Z[x] e como provo que MDC{x,1} = 1. Gostaria de saber também mais duas coisas: i) como defininir a noção de irredutibilidade em um domínio D; ii) usando o teorema da fatoração única (para polinômios), como posso definir o MMC de polinômios. Obs.: Z = {números inteiros} Grato desde já com a possível ajuda de vocês.- Yahoo! Messenger - Fale com seus amigos online. Instale agora!Atenciosammente,Engenharia Elétrica - UNESP Ilha SolteiraOsvaldo Mello Sponquiado Usuário de GNU/Linux__Acabe com aquelas janelinhas que pulam na sua tela.AntiPop-up UOL - É grátis!http://antipopup.uol.com.br/=Instruções para entrar na lista, sair da lista e usar a lista emhttp://www.mat.puc-rio.br/~nicolau/olimp/obm-l.html=Yahoo! Messenger - Fale com seus amigos online. Instale agora!
Re:[obm-l] mdc
ops, corrigindo... 1 é elem. neutro em rel. à multiplicação. Bom se x é inteiro, posso expressá-lo como x=p(1)^k (1).p(2)^k(2). ... .p(n)^k(n) pelo T. fat. única. onde p(i) denota um certo número primo e k(i) denota um natural, com i pertencente ao cjto. {1,2,...,n) 1 é divisível somente pelos inteiros -1 e +1 Logo seu maior divisor é o número 1. x pode ser um número composto ou um primo. Em qualquer um dos casos, teremos que x=x.1 pois no corpo dos números inteiros 1 é o elemento neutro em relação à adição. Assim parece-me trivial pois x e 1 tem 1 e -1 como divisores comuns, portanto o maior divisor comum entre eles é certamento o número 1. Além disso você pode utilizar esse fato aqui: xe y são inteiros O mdc entre x e x-1 é 1 logo pelas props. do mdc temos que mdc(a,a-1)=1=mdc(a,a-1-(a))=mdc(a,-1)=mdc(a,1) Gostaria de saber como defino a noção de MDC em Z [x] e como provo que MDC{x,1} = 1. Gostaria de saber também mais duas coisas: i) como defininir a noção de irredutibilidade em um domínio D; ii) usando o teorema da fatoração única (para polinômios), como posso definir o MMC de polinômios. Obs.: Z = {números inteiros} Grato desde já com a possível ajuda de vocês. - Yahoo! Messenger - Fale com seus amigos online. Instale agora! Atenciosamente, Engenharia Elétrica - UNESP Ilha Solteira Osvaldo Mello Sponquiado Usuário de GNU/Linux ___ ___ Acabe com aquelas janelinhas que pulam na sua tela. AntiPop-up UOL - É grátis! http://antipopup.uol.com.br/ === == Instruções para entrar na lista, sair da lista e usar a lista em http://www.mat.puc-rio.br/~nicolau/olimp/obm-l.html === == Atenciosamente, Engenharia Elétrica - UNESP Ilha Solteira Osvaldo Mello Sponquiado Usuário de GNU/Linux __ Acabe com aquelas janelinhas que pulam na sua tela. AntiPop-up UOL - É grátis! http://antipopup.uol.com.br/ = Instruções para entrar na lista, sair da lista e usar a lista em http://www.mat.puc-rio.br/~nicolau/olimp/obm-l.html =
Re: [obm-l] MDC de Impares
Por metra imposiçao sem muitas especificaçoes.Da pra dividir por dois e nada muda mesmo...Anderson [EMAIL PROTECTED] wrote: Pq da restricao a e b impares? Parece que a demonstracao vale tambem para pares. Carlos Maçaranduba wrote: Como provo que , dado a e b tais que a e b impares positivos e a b, sendo d = mdc(a,b) , entao d tambem poderá ser d = mdc(a - b , b) Se d=mdc(a,b), então a=Ad e b=Bd, e mdc(A,B)=1. Logo mdc(a-b,b)=mdc(Ad-Bd,Bd)=d.mdc(A-B,B) Vamos agora por contradição: Suponha que mdc(A-B,B)=k, com k diferente de 1. Então A-B=rk e B=sk. Mas isso implica em A=rk+B=rk+sk=(r+s)k. Logo k é fator comum de A e B, portanto mdc(A,B)=k, o que contradiz a hipótese de mdc(A,B)=1. Logo mdc(A-B,B)=1 e com isso concluímos que mdc(a-b,b)=d.1=d__Acabe com aquelas janelinhas que pulam na sua tela.AntiPop-up UOL - É grátis!http://antipopup.uol.com.br/=Instruções para entrar na lista, sair da lista e usar a lista emhttp://www.mat.puc-rio.br/~nicolau/olimp/obm-l.html=Yahoo! Mail - 6MB, anti-spam e antivírus gratuito. Crie sua conta agora!
Re: [obm-l] MDC de Impares
Pq da restricao a e b impares? Parece que a demonstracao vale tambem para pares. Carlos Maçaranduba wrote: Como provo que , dado a e b tais que a e b impares positivos e a b, sendo d = mdc(a,b) , entao d tambem poderá ser d = mdc(a - b , b) Se d=mdc(a,b), então a=Ad e b=Bd, e mdc(A,B)=1. Logo mdc(a-b,b)=mdc(Ad-Bd,Bd)=d.mdc(A-B,B) Vamos agora por contradição: Suponha que mdc(A-B,B)=k, com k diferente de 1. Então A-B=rk e B=sk. Mas isso implica em A=rk+B=rk+sk=(r+s)k. Logo k é fator comum de A e B, portanto mdc(A,B)=k, o que contradiz a hipótese de mdc(A,B)=1. Logo mdc(A-B,B)=1 e com isso concluímos que mdc(a- b,b)=d.1=d __ Acabe com aquelas janelinhas que pulam na sua tela. AntiPop-up UOL - É grátis! http://antipopup.uol.com.br/ = Instruções para entrar na lista, sair da lista e usar a lista em http://www.mat.puc-rio.br/~nicolau/olimp/obm-l.html =
Re: [obm-l] MDC de Impares
Carlos Maçaranduba wrote: Como provo que , dado a e b tais que a e b impares positivos e a b, sendo d = mdc(a,b) , entao d tambem poderá ser d = mdc(a - b , b) Se d=mdc(a,b), então a=Ad e b=Bd, e mdc(A,B)=1. Logo mdc(a-b,b)=mdc(Ad-Bd,Bd)=d.mdc(A-B,B) Vamos agora por contradição: Suponha que mdc(A-B,B)=k, com k diferente de 1. Então A-B=rk e B=sk. Mas isso implica em A=rk+B=rk+sk=(r+s)k. Logo k é fator comum de A e B, portanto mdc(A,B)=k, o que contradiz a hipótese de mdc(A,B)=1. Logo mdc(A-B,B)=1 e com isso concluímos que mdc(a-b,b)=d.1=d Ricardo Bittencourt http://www.mundobizarro.tk [EMAIL PROTECTED]Vitrum edere possum, mihi non nocet -- União contra o forward - crie suas proprias piadas -- = Instruções para entrar na lista, sair da lista e usar a lista em http://www.mat.puc-rio.br/~nicolau/olimp/obm-l.html =
Re: [obm-l] Mdc, mdc e mmc
Olá! Como 4 divide 8 e 12, 4 é o mdc. Por outro lado, 8 nao divide 12, mas divide 24. Logo, 24 é o mmc. Por fim, como nao se divide por zero,1 deverá ser o menor divisor comum. Item c. Fui! Tertuliano Carneiro. Marcelo Roseira [EMAIL PROTECTED] wrote: O máximo divisor comum, o menor divisor comum e o mínimo múltiplo comum dos números 4, 8 e 12, são, respectivamente: a) 2, 1 e 12 b) 4, 2 e 12 c) 4, 1 e 24 d) 12, 2 e 24 e) 12, 4 e 48 Grato.Yahoo! GeoCities Tudo para criar o seu site: ferramentas fáceis de usar, espaço de sobra e acessórios.