Suponha que p é divisor de ab, mas não seja de a.
Então a e p serão primos entre si, e assim podemos achar x e y tais que
xa+yp=1
Multiplicando por b, temos
xab+ybp=b
Como xab e ybp são múltiplos de p, a soma também será. É isso!
Em 15/10/10, luizluizvalve...@globo.com escreveu:
Alguem pode me
Alguem pode me ajudar.?
O algoritmo de Euclides estendido é o seguinte:
Dados a e b inteiros, seja d = mdc(a,b) então existem r e s inteiros tais que
sa+rb=d.
Usando o algoritmo de Euclides estendido mostre que se p é primo e a e b são
inteiros tais que p é divisor de ab, então p é
2 matches
Mail list logo