[obm-l] Re: [obm-l] Re: [obm-l] Equação diofantina
Na verdade Pedro eu parti do princípio que ao ler minha pergunta vcs iriam ler a solução que está no link que deixei ´na pergunta, e lá no link está claro que ele toma valores de x>=4, foi mal! Em 15 de outubro de 2015 16:05, Israel Meireles Chrisostomo < israelmchrisost...@gmail.com> escreveu: > Pessoal, gostaria de agradecer ao pessoal do grupo, vcs são demais, vcs > entendem muito e raciocinam para kralho!Além disso são humildes ao > responderem minhas dúvidas, vcs são 10! > > Em 15 de outubro de 2015 15:43, Pedro Joséescreveu: > >> Boa tarde! >> >> Fácil de achar há duas soluções. (1,0); (3,2). Não sei se são únicas. >> Porém, nem 0 nem 2 são congruentes a 20 (mod54). >> Procure expressar melhor o que você deseja. >> >> >> >> Mas quanto ao seu questionamento que há um período na função 5^y, onde a >> congruência se repete... >> >> Teorema de Euler-Fermat: Se mdc(a,m) = 1==> a^Ф(m) ≡ 1 (mod m), onde Ф(m) >> é a função totiente de Euler que nada mais é que a quantidade de 0> tal que mdc(d,m) = 1., ou seja, a cardinalidade do grupo (Z /Zm)*. >> Para calcular Ф(m), onde a fatoração de m é p1^y1 * p2^y2 *...* pn^yn >> teremos: >> Ф(m)=m *(1-1/p1)*(1-1/p2)*...*(1-1/pn) (i) >> >> assim para m=81, como mdc (5,81) =1 temos por Euler-Fermat que 5^Ф(81) ≡ >> 1 (mod 81), >> >> 81= 3^4, logo por (i) Ф(81) = 81 (2/3)= 54 ==> 5^54 ≡ 1 (mod 81), ==> >> 5^p+n*54 ≡ 5^p*(5^54)^n (mod 81), >> ==> 5^p+n*54 ≡ 5^p*(1)^n ≡ 5^p (mod 81) >> >> Porém, Ф(m) não é necessariamente o mínimo valor de p em que ocorre a^p ≡ >> 1 (mod m),. >> >> Definição: sejam a,m inteiros e mdc(a,m) = 1. A ordem de a módulo m, >> representada por ordma, é o menor inteiro d > 0 tal que; a^d ≡ 1 (mod >> m). >> >> Portanto temos que: ordma divide Ф(m). >> >> E quando ordma = Ф(m), dizemos que a é uma raiz primitiva de m. >> >> No caso 5 é uma raiz primitiva de 3^4 =81. >> >> Recomendo você dar uma lida: >> http://www.icmc.usp.br/~etengan/imersao/imersao.pdf >> >> Saudações, >> PJMS. >> >> >> >> >> >> >> >> Saudações. >> >> Em 15 de outubro de 2015 13:53, Israel Meireles Chrisostomo < >> israelmchrisost...@gmail.com> escreveu: >> >>> Não quero que resolvam a equação pois já tenho a solução, só quero >>> entender uma parte da solução...Na equação 3^x-5^y=2, como posso concluir >>> que y é congruente 20 módulo 54(sem fazer todas as congruências é >>> claro)?Alguém poderia me explicar como concluir isso de forma simples? >>> Aqui está a solução da equação diofantina: >>> http://diego.mat.unb.br/click.html >>> No caso ele fez a congruência módulo 81 e concluiu que 5^y é congruente >>> a -2 que é congruente 79 módulo 81(até aqui tudo bem), e depois daí partiu >>> para dizer que y é congruente a 20 módulo 54.Mas sinceramente para eu >>> concluir isso eu teria que fazer todas as congruências de 5^y módulo 81 >>> até que percebesse que na vez 54 a congruência daria 1 e daí em diante se >>> repetiria, mas eu tenho a impressão que ele não fez todas as congruências >>> módulo 81 para concluir isso, isso simplesmente seria inviável por ser >>> impensável.Então, como ele conclui fazendo congruência módulo 81 que as >>> potências de 5 deixam o mesmo resto módulo 81 a cada 54 vezes?Se alguém >>> pudesse me explicar ficaria muito grato, teoria dos números é algo novo >>> para mim, desde já agradeço! >>> >>> -- >>> 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. > > > -- Esta mensagem foi verificada pelo sistema de antiv�rus e acredita-se estar livre de perigo.
[obm-l] Re: [obm-l] Re: [obm-l] Equação diofantina
Pessoal, gostaria de agradecer ao pessoal do grupo, vcs são demais, vcs entendem muito e raciocinam para kralho!Além disso são humildes ao responderem minhas dúvidas, vcs são 10! Em 15 de outubro de 2015 15:43, Pedro Joséescreveu: > Boa tarde! > > Fácil de achar há duas soluções. (1,0); (3,2). Não sei se são únicas. > Porém, nem 0 nem 2 são congruentes a 20 (mod54). > Procure expressar melhor o que você deseja. > > > > Mas quanto ao seu questionamento que há um período na função 5^y, onde a > congruência se repete... > > Teorema de Euler-Fermat: Se mdc(a,m) = 1==> a^Ф(m) ≡ 1 (mod m), onde Ф(m) > é a função totiente de Euler que nada mais é que a quantidade de 0 tal que mdc(d,m) = 1., ou seja, a cardinalidade do grupo (Z /Zm)*. > Para calcular Ф(m), onde a fatoração de m é p1^y1 * p2^y2 *...* pn^yn > teremos: > Ф(m)=m *(1-1/p1)*(1-1/p2)*...*(1-1/pn) (i) > > assim para m=81, como mdc (5,81) =1 temos por Euler-Fermat que 5^Ф(81) ≡ > 1 (mod 81), > > 81= 3^4, logo por (i) Ф(81) = 81 (2/3)= 54 ==> 5^54 ≡ 1 (mod 81), ==> > 5^p+n*54 ≡ 5^p*(5^54)^n (mod 81), > ==> 5^p+n*54 ≡ 5^p*(1)^n ≡ 5^p (mod 81) > > Porém, Ф(m) não é necessariamente o mínimo valor de p em que ocorre a^p ≡ 1 > (mod m),. > > Definição: sejam a,m inteiros e mdc(a,m) = 1. A ordem de a módulo m, > representada por ordma, é o menor inteiro d > 0 tal que; a^d ≡ 1 (mod m). > > Portanto temos que: ordma divide Ф(m). > > E quando ordma = Ф(m), dizemos que a é uma raiz primitiva de m. > > No caso 5 é uma raiz primitiva de 3^4 =81. > > Recomendo você dar uma lida: > http://www.icmc.usp.br/~etengan/imersao/imersao.pdf > > Saudações, > PJMS. > > > > > > > > Saudações. > > Em 15 de outubro de 2015 13:53, Israel Meireles Chrisostomo < > israelmchrisost...@gmail.com> escreveu: > >> Não quero que resolvam a equação pois já tenho a solução, só quero >> entender uma parte da solução...Na equação 3^x-5^y=2, como posso concluir >> que y é congruente 20 módulo 54(sem fazer todas as congruências é >> claro)?Alguém poderia me explicar como concluir isso de forma simples? >> Aqui está a solução da equação diofantina: >> http://diego.mat.unb.br/click.html >> No caso ele fez a congruência módulo 81 e concluiu que 5^y é congruente a >> -2 que é congruente 79 módulo 81(até aqui tudo bem), e depois daí partiu >> para dizer que y é congruente a 20 módulo 54.Mas sinceramente para eu >> concluir isso eu teria que fazer todas as congruências de 5^y módulo 81 >> até que percebesse que na vez 54 a congruência daria 1 e daí em diante se >> repetiria, mas eu tenho a impressão que ele não fez todas as congruências >> módulo 81 para concluir isso, isso simplesmente seria inviável por ser >> impensável.Então, como ele conclui fazendo congruência módulo 81 que as >> potências de 5 deixam o mesmo resto módulo 81 a cada 54 vezes?Se alguém >> pudesse me explicar ficaria muito grato, teoria dos números é algo novo >> para mim, desde já agradeço! >> >> -- >> 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. -- Esta mensagem foi verificada pelo sistema de antiv�rus e acredita-se estar livre de perigo.
[obm-l] Re: [obm-l] Re: [obm-l] equação diofantina
ah sim é verdade! Em 14 de outubro de 2015 11:20, Gabriel Tostesescreveu: > (1,0) nao eh solucao tbm? > > > > Sent from my iPad > On Oct 14, 2015, at 11:04, Israel Meireles Chrisostomo < > israelmchrisost...@gmail.com> wrote: > > Está aqui no site do professor Diego Marques: > http://diego.mat.unb.br/click.html > Só possui uma solução, que é a solução trivial(x=3 e y=2).Mas  o > difÃcil é provar que a solução é única, veja que raciocÃnio > fantástico! > > Em 14 de outubro de 2015 07:41, marcone augusto araújo borges < > marconeborge...@hotmail.com> escreveu: > >> E a solução da equação 3^x - 5^y = 2 ? >> >> -- >> 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. > > > -- > 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] RE: [obm-l] Re: [obm-l] Equação diofantina (de novo)
Bom dia! Desculpe-me, não vi a restrição do método. Sds, PJMS Em 22 de abril de 2015 12:04, Pedro Chaves brped...@hotmail.com escreveu: Obrigado, Pedro José! O que desejo, entretanto, é resolver a equação por congruência. Um abraço! Pedro Chaves Date: Wed, 22 Apr 2015 11:32:17 -0300 Subject: [obm-l] Re: [obm-l] Equação diofantina (de novo) From: petroc...@gmail.com To: obm-l@mat.puc-rio.br Bom dia! Pelo teorema de Bèzout a equação ax + by = c tem solução se e somente se m.d.c.(a,b) divide c. Como 7 e 12 são primos entre si, temos que 1 divide 11 e tem solução. Primeiro passo achar o m.d.c. entre 7 e 12 pelo algorítimo de Euclides. 12 = 7 * 1 + 5 7 = 5 * 1 + 2 5 = 2 * 2 + 1 Segundo passo: expressar a unidade como uma Z combinação linear de 12 e 7. (embora para o caso seja fácil achar 1 = 3 * 12 - 7 * 5, faremos de modo sistemático, pois as vezez não o é fácil.) 5 = 12 - 7 (i) 2 = 7 - 5 (ii) 1 = 5 - 2 *2 (iii) (ii) e (iii) == 1 = 5 - ( 7 -5) *2 = 3*5 - 7 * 2 (iv) (iv) e (i) == 1 = 3 * (12 - 7) - 7*2 = 3 * 12 - 7 * 5 então podemos afirmar que - 5 *7 -12 * (-3) =1. então (-5,-3) é uma solução da equação : 7x -12 y = 1 Se multiplicarmos por 11, teremos que (-55,-33) é uma solução da equação 7 x - 12 y = 11. Agora use a solução encontrada 7 x - 12 y = 7 * (-55) - 12 * (-33) == 7 * (x+55) = 12 (y+33) (v) pelo fechamento da adição em Z temos que 7 divide 12 (y +33) Usando o teorema: se d divede ab e m.d.c.(d,a) = 1 == d divide b. m.d.c (7,12) = 1 == 7 divide (y+33) == existe t Ɛ Z, 7* t = (y+33) == y = -33 + 7*t (vi) (vi) e (v) == 7* (x+55) = 12 * 7*T) == x = -55 +12*t Então a solução completa é { (x,y) Ɛ Z^2 | x= -55+ 12*t , y = -33 + 7*t, t ƐZ } Caso os coeficientes a e b, da equação a x+ by = c, não sejam primos entre si, para que se possa aplicar o destacado em vermelho, basta dividir todos os membros por m.d.c(a,b), pois por Bèzout só existem soluções se m.d.c.(a,b) divide c. Tem o artigo do eduardo Tengan: http://www.icmc.usp.br/~etengan/imersao/imersao.pdf, onde há demonstrações e muito mais. Foi lá que aprendi a resolver essas equações. Saudações, PJMS Em 22 de abril de 2015 07:43, Benedito Tadeu V. Freire b...@ccet.ufrn.brmailto:b...@ccet.ufrn.br escreveu: Pedro, 7 é o inverso de 7 módulo 12 -- Open WebMail Project (http://openwebmail.orghttp://openwebmail.org/) -- Original Message --- From: Pedro Chaves brped...@hotmail.commailto:brped...@hotmail.com To: obm-l@mat.puc-rio.brmailto:obm-l@mat.puc-rio.br obm-l@mat.puc-rio.brmailto:obm-l@mat.puc-rio.br Sent: Wed, 22 Apr 2015 12:46:28 +0300 Subject: [obm-l] Equação diofantina (de novo) Caros Colegas, A equação diofantina 7x - 12y = 11 pode ser resolvida por congruência? Não consegui. Sei que 7x é congruente a -1 (mod 12), mas não sei como ir em frente. Abraços. 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 = --- End of Original Message --- -- 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. -- 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.
[obm-l] RE: [obm-l] Re: [obm-l] Equação diofantina (de novo)
Obrigado, Pedro José! O que desejo, entretanto, é resolver a equação por congruência. Um abraço! Pedro Chaves Date: Wed, 22 Apr 2015 11:32:17 -0300 Subject: [obm-l] Re: [obm-l] Equação diofantina (de novo) From: petroc...@gmail.com To: obm-l@mat.puc-rio.br Bom dia! Pelo teorema de Bèzout a equação ax + by = c tem solução se e somente se m.d.c.(a,b) divide c. Como 7 e 12 são primos entre si, temos que 1 divide 11 e tem solução. Primeiro passo achar o m.d.c. entre 7 e 12 pelo algorítimo de Euclides. 12 = 7 * 1 + 5 7 = 5 * 1 + 2 5 = 2 * 2 + 1 Segundo passo: expressar a unidade como uma Z combinação linear de 12 e 7. (embora para o caso seja fácil achar 1 = 3 * 12 - 7 * 5, faremos de modo sistemático, pois as vezez não o é fácil.) 5 = 12 - 7 (i) 2 = 7 - 5 (ii) 1 = 5 - 2 *2 (iii) (ii) e (iii) == 1 = 5 - ( 7 -5) *2 = 3*5 - 7 * 2 (iv) (iv) e (i) == 1 = 3 * (12 - 7) - 7*2 = 3 * 12 - 7 * 5 então podemos afirmar que - 5 *7 -12 * (-3) =1. então (-5,-3) é uma solução da equação : 7x -12 y = 1 Se multiplicarmos por 11, teremos que (-55,-33) é uma solução da equação 7 x - 12 y = 11. Agora use a solução encontrada 7 x - 12 y = 7 * (-55) - 12 * (-33) == 7 * (x+55) = 12 (y+33) (v) pelo fechamento da adição em Z temos que 7 divide 12 (y +33) Usando o teorema: se d divede ab e m.d.c.(d,a) = 1 == d divide b. m.d.c (7,12) = 1 == 7 divide (y+33) == existe t Ɛ Z, 7* t = (y+33) == y = -33 + 7*t (vi) (vi) e (v) == 7* (x+55) = 12 * 7*T) == x = -55 +12*t Então a solução completa é { (x,y) Ɛ Z^2 | x= -55+ 12*t , y = -33 + 7*t, t ƐZ } Caso os coeficientes a e b, da equação a x+ by = c, não sejam primos entre si, para que se possa aplicar o destacado em vermelho, basta dividir todos os membros por m.d.c(a,b), pois por Bèzout só existem soluções se m.d.c.(a,b) divide c. Tem o artigo do eduardo Tengan: http://www.icmc.usp.br/~etengan/imersao/imersao.pdf, onde há demonstrações e muito mais. Foi lá que aprendi a resolver essas equações. Saudações, PJMS Em 22 de abril de 2015 07:43, Benedito Tadeu V. Freire b...@ccet.ufrn.brmailto:b...@ccet.ufrn.br escreveu: Pedro, 7 é o inverso de 7 módulo 12 -- Open WebMail Project (http://openwebmail.orghttp://openwebmail.org/) -- Original Message --- From: Pedro Chaves brped...@hotmail.commailto:brped...@hotmail.com To: obm-l@mat.puc-rio.brmailto:obm-l@mat.puc-rio.br obm-l@mat.puc-rio.brmailto:obm-l@mat.puc-rio.br Sent: Wed, 22 Apr 2015 12:46:28 +0300 Subject: [obm-l] Equação diofantina (de novo) Caros Colegas, A equação diofantina 7x - 12y = 11 pode ser resolvida por congruência? Não consegui. Sei que 7x é congruente a -1 (mod 12), mas não sei como ir em frente. Abraços. 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 = --- End of Original Message --- -- 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. -- 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] RE: [obm-l] Re: [obm-l] Equação diofantina (de novo)
Boa tarde! Corrigindo... y = 2 + 7m e não 2+ 2m. Desculpem-me, PJMS Em 22 de abril de 2015 14:26, Pedro José petroc...@gmail.com escreveu: Boa tarde! Não parei para pensar se dá sempre. 7 * x ≡ 11 (mod12) == 7*7*x ≡ -1*7 (mod12) == x ≡ 5 (mod12) == x = 5 + 12* m : m Ɛ Z -12*y ≡11 (mod7) == 2*y ≡ 4 (mod7) == 4*2*y ≡ 4*4 (mod7) == y ≡ 2 (mod12) == y =2 + 7*n : n ƐZ Substituindo na equação original temos: 7 * (5 +12*m) -12* (2 + 7*n) =11 == 84*m - 84* n = 0 == m=n == x = 5 +12 m e y = 2 + 2m : m ƐZ. Saudações, PJMS Em 22 de abril de 2015 13:37, Pedro José petroc...@gmail.com escreveu: Bom dia! Desculpe-me, não vi a restrição do método. Sds, PJMS Em 22 de abril de 2015 12:04, Pedro Chaves brped...@hotmail.com escreveu: Obrigado, Pedro José! O que desejo, entretanto, é resolver a equação por congruência. Um abraço! Pedro Chaves Date: Wed, 22 Apr 2015 11:32:17 -0300 Subject: [obm-l] Re: [obm-l] Equação diofantina (de novo) From: petroc...@gmail.com To: obm-l@mat.puc-rio.br Bom dia! Pelo teorema de Bèzout a equação ax + by = c tem solução se e somente se m.d.c.(a,b) divide c. Como 7 e 12 são primos entre si, temos que 1 divide 11 e tem solução. Primeiro passo achar o m.d.c. entre 7 e 12 pelo algorítimo de Euclides. 12 = 7 * 1 + 5 7 = 5 * 1 + 2 5 = 2 * 2 + 1 Segundo passo: expressar a unidade como uma Z combinação linear de 12 e 7. (embora para o caso seja fácil achar 1 = 3 * 12 - 7 * 5, faremos de modo sistemático, pois as vezez não o é fácil.) 5 = 12 - 7 (i) 2 = 7 - 5 (ii) 1 = 5 - 2 *2 (iii) (ii) e (iii) == 1 = 5 - ( 7 -5) *2 = 3*5 - 7 * 2 (iv) (iv) e (i) == 1 = 3 * (12 - 7) - 7*2 = 3 * 12 - 7 * 5 então podemos afirmar que - 5 *7 -12 * (-3) =1. então (-5,-3) é uma solução da equação : 7x -12 y = 1 Se multiplicarmos por 11, teremos que (-55,-33) é uma solução da equação 7 x - 12 y = 11. Agora use a solução encontrada 7 x - 12 y = 7 * (-55) - 12 * (-33) == 7 * (x+55) = 12 (y+33) (v) pelo fechamento da adição em Z temos que 7 divide 12 (y +33) Usando o teorema: se d divede ab e m.d.c.(d,a) = 1 == d divide b. m.d.c (7,12) = 1 == 7 divide (y+33) == existe t Ɛ Z, 7* t = (y+33) == y = -33 + 7*t (vi) (vi) e (v) == 7* (x+55) = 12 * 7*T) == x = -55 +12*t Então a solução completa é { (x,y) Ɛ Z^2 | x= -55+ 12*t , y = -33 + 7*t, t ƐZ } Caso os coeficientes a e b, da equação a x+ by = c, não sejam primos entre si, para que se possa aplicar o destacado em vermelho, basta dividir todos os membros por m.d.c(a,b), pois por Bèzout só existem soluções se m.d.c.(a,b) divide c. Tem o artigo do eduardo Tengan: http://www.icmc.usp.br/~etengan/imersao/imersao.pdf, onde há demonstrações e muito mais. Foi lá que aprendi a resolver essas equações. Saudações, PJMS Em 22 de abril de 2015 07:43, Benedito Tadeu V. Freire b...@ccet.ufrn.brmailto:b...@ccet.ufrn.br escreveu: Pedro, 7 é o inverso de 7 módulo 12 -- Open WebMail Project (http://openwebmail.orghttp://openwebmail.org/) -- Original Message --- From: Pedro Chaves brped...@hotmail.commailto:brped...@hotmail.com To: obm-l@mat.puc-rio.brmailto:obm-l@mat.puc-rio.br obm-l@mat.puc-rio.brmailto:obm-l@mat.puc-rio.br Sent: Wed, 22 Apr 2015 12:46:28 +0300 Subject: [obm-l] Equação diofantina (de novo) Caros Colegas, A equação diofantina 7x - 12y = 11 pode ser resolvida por congruência? Não consegui. Sei que 7x é congruente a -1 (mod 12), mas não sei como ir em frente. Abraços. 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 = --- End of Original Message --- -- 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. -- 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.
[obm-l] Re: [obm-l] RE: [obm-l] Re: [obm-l] Equação diofantina (de novo)
Boa tarde! Não parei para pensar se dá sempre. 7 * x ≡ 11 (mod12) == 7*7*x ≡ -1*7 (mod12) == x ≡ 5 (mod12) == x = 5 + 12* m : m Ɛ Z -12*y ≡11 (mod7) == 2*y ≡ 4 (mod7) == 4*2*y ≡ 4*4 (mod7) == y ≡ 2 (mod12) == y =2 + 7*n : n ƐZ Substituindo na equação original temos: 7 * (5 +12*m) -12* (2 + 7*n) =11 == 84*m - 84* n = 0 == m=n == x = 5 +12 m e y = 2 + 2m : m ƐZ. Saudações, PJMS Em 22 de abril de 2015 13:37, Pedro José petroc...@gmail.com escreveu: Bom dia! Desculpe-me, não vi a restrição do método. Sds, PJMS Em 22 de abril de 2015 12:04, Pedro Chaves brped...@hotmail.com escreveu: Obrigado, Pedro José! O que desejo, entretanto, é resolver a equação por congruência. Um abraço! Pedro Chaves Date: Wed, 22 Apr 2015 11:32:17 -0300 Subject: [obm-l] Re: [obm-l] Equação diofantina (de novo) From: petroc...@gmail.com To: obm-l@mat.puc-rio.br Bom dia! Pelo teorema de Bèzout a equação ax + by = c tem solução se e somente se m.d.c.(a,b) divide c. Como 7 e 12 são primos entre si, temos que 1 divide 11 e tem solução. Primeiro passo achar o m.d.c. entre 7 e 12 pelo algorítimo de Euclides. 12 = 7 * 1 + 5 7 = 5 * 1 + 2 5 = 2 * 2 + 1 Segundo passo: expressar a unidade como uma Z combinação linear de 12 e 7. (embora para o caso seja fácil achar 1 = 3 * 12 - 7 * 5, faremos de modo sistemático, pois as vezez não o é fácil.) 5 = 12 - 7 (i) 2 = 7 - 5 (ii) 1 = 5 - 2 *2 (iii) (ii) e (iii) == 1 = 5 - ( 7 -5) *2 = 3*5 - 7 * 2 (iv) (iv) e (i) == 1 = 3 * (12 - 7) - 7*2 = 3 * 12 - 7 * 5 então podemos afirmar que - 5 *7 -12 * (-3) =1. então (-5,-3) é uma solução da equação : 7x -12 y = 1 Se multiplicarmos por 11, teremos que (-55,-33) é uma solução da equação 7 x - 12 y = 11. Agora use a solução encontrada 7 x - 12 y = 7 * (-55) - 12 * (-33) == 7 * (x+55) = 12 (y+33) (v) pelo fechamento da adição em Z temos que 7 divide 12 (y +33) Usando o teorema: se d divede ab e m.d.c.(d,a) = 1 == d divide b. m.d.c (7,12) = 1 == 7 divide (y+33) == existe t Ɛ Z, 7* t = (y+33) == y = -33 + 7*t (vi) (vi) e (v) == 7* (x+55) = 12 * 7*T) == x = -55 +12*t Então a solução completa é { (x,y) Ɛ Z^2 | x= -55+ 12*t , y = -33 + 7*t, t ƐZ } Caso os coeficientes a e b, da equação a x+ by = c, não sejam primos entre si, para que se possa aplicar o destacado em vermelho, basta dividir todos os membros por m.d.c(a,b), pois por Bèzout só existem soluções se m.d.c.(a,b) divide c. Tem o artigo do eduardo Tengan: http://www.icmc.usp.br/~etengan/imersao/imersao.pdf, onde há demonstrações e muito mais. Foi lá que aprendi a resolver essas equações. Saudações, PJMS Em 22 de abril de 2015 07:43, Benedito Tadeu V. Freire b...@ccet.ufrn.brmailto:b...@ccet.ufrn.br escreveu: Pedro, 7 é o inverso de 7 módulo 12 -- Open WebMail Project (http://openwebmail.orghttp://openwebmail.org/) -- Original Message --- From: Pedro Chaves brped...@hotmail.commailto:brped...@hotmail.com To: obm-l@mat.puc-rio.brmailto:obm-l@mat.puc-rio.br obm-l@mat.puc-rio.brmailto:obm-l@mat.puc-rio.br Sent: Wed, 22 Apr 2015 12:46:28 +0300 Subject: [obm-l] Equação diofantina (de novo) Caros Colegas, A equação diofantina 7x - 12y = 11 pode ser resolvida por congruência? Não consegui. Sei que 7x é congruente a -1 (mod 12), mas não sei como ir em frente. Abraços. 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 = --- End of Original Message --- -- 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. -- 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.
[obm-l] RE: [obm-l] Re: [obm-l] RE: [obm-l] Re: [obm-l] Equação diofantina (de novo)
Obrigado a todos! Pedro Chaves __ Date: Wed, 22 Apr 2015 14:32:35 -0300 Subject: [obm-l] Re: [obm-l] RE: [obm-l] Re: [obm-l] Equação diofantina (de novo) From: petroc...@gmail.com To: obm-l@mat.puc-rio.br Boa tarde! Corrigindo... y = 2 + 7m e não 2+ 2m. Desculpem-me, PJMS Em 22 de abril de 2015 14:26, Pedro José petroc...@gmail.commailto:petroc...@gmail.com escreveu: Boa tarde! Não parei para pensar se dá sempre. 7 * x ≡ 11 (mod12) == 7*7*x ≡ -1*7 (mod12) == x ≡ 5 (mod12) == x = 5 + 12* m : m Ɛ Z -12*y ≡11 (mod7) == 2*y ≡ 4 (mod7) == 4*2*y ≡ 4*4 (mod7) == y ≡ 2 (mod12) == y =2 + 7*n : n ƐZ Substituindo na equação original temos: 7 * (5 +12*m) -12* (2 + 7*n) =11 == 84*m - 84* n = 0 == m=n == x = 5 +12 m e y = 2 + 2m : m ƐZ. Saudações, PJMS Em 22 de abril de 2015 13:37, Pedro José petroc...@gmail.commailto:petroc...@gmail.com escreveu: Bom dia! Desculpe-me, não vi a restrição do método. Sds, PJMS Em 22 de abril de 2015 12:04, Pedro Chaves brped...@hotmail.commailto:brped...@hotmail.com escreveu: Obrigado, Pedro José! O que desejo, entretanto, é resolver a equação por congruência. Um abraço! Pedro Chaves Date: Wed, 22 Apr 2015 11:32:17 -0300 Subject: [obm-l] Re: [obm-l] Equação diofantina (de novo) From: petroc...@gmail.commailto:petroc...@gmail.com To: obm-l@mat.puc-rio.brmailto:obm-l@mat.puc-rio.br Bom dia! Pelo teorema de Bèzout a equação ax + by = c tem solução se e somente se m.d.c.(a,b) divide c. Como 7 e 12 são primos entre si, temos que 1 divide 11 e tem solução. Primeiro passo achar o m.d.c. entre 7 e 12 pelo algorítimo de Euclides. 12 = 7 * 1 + 5 7 = 5 * 1 + 2 5 = 2 * 2 + 1 Segundo passo: expressar a unidade como uma Z combinação linear de 12 e 7. (embora para o caso seja fácil achar 1 = 3 * 12 - 7 * 5, faremos de modo sistemático, pois as vezez não o é fácil.) 5 = 12 - 7 (i) 2 = 7 - 5 (ii) 1 = 5 - 2 *2 (iii) (ii) e (iii) == 1 = 5 - ( 7 -5) *2 = 3*5 - 7 * 2 (iv) (iv) e (i) == 1 = 3 * (12 - 7) - 7*2 = 3 * 12 - 7 * 5 então podemos afirmar que - 5 *7 -12 * (-3) =1. então (-5,-3) é uma solução da equação : 7x -12 y = 1 Se multiplicarmos por 11, teremos que (-55,-33) é uma solução da equação 7 x - 12 y = 11. Agora use a solução encontrada 7 x - 12 y = 7 * (-55) - 12 * (-33) == 7 * (x+55) = 12 (y+33) (v) pelo fechamento da adição em Z temos que 7 divide 12 (y +33) Usando o teorema: se d divede ab e m.d.c.(d,a) = 1 == d divide b. m.d.c (7,12) = 1 == 7 divide (y+33) == existe t Ɛ Z, 7* t = (y+33) == y = -33 + 7*t (vi) (vi) e (v) == 7* (x+55) = 12 * 7*T) == x = -55 +12*t Então a solução completa é { (x,y) Ɛ Z^2 | x= -55+ 12*t , y = -33 + 7*t, t ƐZ } Caso os coeficientes a e b, da equação a x+ by = c, não sejam primos entre si, para que se possa aplicar o destacado em vermelho, basta dividir todos os membros por m.d.c(a,b), pois por Bèzout só existem soluções se m.d.c.(a,b) divide c. Tem o artigo do eduardo Tengan: http://www.icmc.usp.br/~etengan/imersao/imersao.pdf, onde há demonstrações e muito mais. Foi lá que aprendi a resolver essas equações. Saudações, PJMS Em 22 de abril de 2015 07:43, Benedito Tadeu V. Freire b...@ccet.ufrn.brmailto:b...@ccet.ufrn.brmailto:b...@ccet.ufrn.brmailto:b...@ccet.ufrn.br escreveu: Pedro, 7 é o inverso de 7 módulo 12 -- Open WebMail Project (http://openwebmail.orghttp://openwebmail.org/) -- Original Message --- From: Pedro Chaves brped...@hotmail.commailto:brped...@hotmail.commailto:brped...@hotmail.commailto:brped...@hotmail.com To: obm-l@mat.puc-rio.brmailto:obm-l@mat.puc-rio.brmailto:obm-l@mat.puc-rio.brmailto:obm-l@mat.puc-rio.br obm-l@mat.puc-rio.brmailto:obm-l@mat.puc-rio.brmailto:obm-l@mat.puc-rio.brmailto:obm-l@mat.puc-rio.br Sent: Wed, 22 Apr 2015 12:46:28 +0300 Subject: [obm-l] Equação diofantina (de novo) Caros Colegas, A equação diofantina 7x - 12y = 11 pode ser resolvida por congruência? Não consegui. Sei que 7x é congruente a -1 (mod 12), mas não sei como ir em frente. Abraços. 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 = --- End of Original Message --- -- 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. -- Esta mensagem foi verificada
[obm-l] RE: [obm-l] Re: [obm-l] equação diofantina
Mdc(a,b)=1 -Original Message- From: [EMAIL PROTECTED] [mailto:[EMAIL PROTECTED] On Behalf Of Giselle Sent: Friday, October 24, 2003 2:44 PM To: [EMAIL PROTECTED] Subject: [obm-l] Re: [obm-l] equação diofantina Só uma dúvida, pode parecer idiota, mas o que significa (a,b) = 1? - Original Message - From: luiz frança [EMAIL PROTECTED] To: [EMAIL PROTECTED] Sent: Friday, October 24, 2003 1:53 PM Subject: [obm-l] equação diofantina se (a,b)=1 ax +by = k , x, y e k inteiros porvar que sempre existe uma soluma solução x,y que satisfaça a equação para qualquer k escolhido. será mesmo verdade? bom... a principio se ax +by = 1 tiver solução, então terá pra qualquer K. pois basta pegarmos Kx e Ky. Mas como provar que vale pra k=1 ??? __ Do you Yahoo!? The New Yahoo! Shopping - with improved product search http://shopping.yahoo.com = 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 = = 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 = = 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 =