드래그 앤 드롭으로
즐겨찾기 아이콘 위치 수정이 가능합니다.
게시물ID : jisik_86891짧은주소 복사하기
작성자 : 강두★
추천 : 0
조회수 : 738회
댓글수 : 0개
등록시간 : 2010/10/17 18:16:34
유클리드 알고리즘을 이용한 문제를 풀고있는데 도저히 모르겠습니다.
두정수 102와 222 의 최대공약수와 그 최대공약수를 d라고하면
d = 102s + 222t 가 되는 정수 s, t를 구하는 문제입니다.
유클리드알고리즘에 의해서 먼저 최대공약수를 구하면
222 = 102*2+18,
102 = 18*5+12,
18 = 12*1+6,
12 = 6*2+0
위 식에서 0이아닌 마지막 나머지가 6이기때문에 최대공약수 d는 6이되는것까진 이해가됩니다
근데 그다음 정수 s, t 를 구하는부분에서 막힙니다.
위에있는
222 = 102*2+18,
102 = 18*5+12,
18 = 12*1+6,
이 식을 역으로 이용해서 나머지 6, 12, 18을 차례로 소거하면서 다음과같이 구하라는데...
6 = 18-12*1
= 18-(102-18*5)
= 6*18-102
= 6*(222-102*2)-102
= 6*222+(-13)*102
이렇게되서 d = 102s + 222t 를 만족하는 정수 s, t가
s = -13, t= 6 이라고는하는데
이걸 어떤식으로 풀어논건지 도저히 이해를못하겠습니다
답변좀 부탁드릴께요
댓글 분란 또는 분쟁 때문에
전체 댓글이 블라인드 처리되었습니다.
새로운 댓글이 없습니다.