ax ≡ 1 (mod m) 유클리드 호제법으로 푼다. (a=11, m= 19) 19 = 1 * 11 + 8 11 = 1 * 8 + 3 8 = 2 * 3 + 2 3 = 1 * 2 + 1 q = [0, 1, 1, 2, 1] 시작값 0을 넣고, q값 나열 t = [1, ?, ?, ?, ?] 시작값은 1로 한다 다음 t값을 채우는 방법 : 위쪽값*왼쪽값 + 왼위값 q = [0, 1, 1, 2, 1] t = [1, 1, 2, 5, 7] 여기서 짝수 번째의 t 값은 음수를 취한다 t = [1, -1, 2, -5, 7] x ≡ 7 (mod 19) 세로로 쓰면 [n] [q] [t] [19] [0] [1] [11] [1] [1] [8] [1] [2] [3] [2] [5] [2] [1] [7] [1]