p | ab이면 p | a 혹은 p | b 이다. $gcd(a,b) = xa + yb$ 먼저 $gcd(a,b) = xa + yb$를 전제로 해야 한다. 증명은 이렇게 된다. p | ab이면 p | a 혹은 p | b 이다. 어찌보면 당연한 소리인데, 증명을 할 수 있다. 아래와 같은 케이스로 나눠보자. p | a가 맞음 -> 증명 완료 p | a가 아님 -> p는 소수이니 gcd(p, a) = 1 or p 이다. gcd(p, a) = p -> a = kp이니 p | a가 맞다. -> 불가능. gcd(p, a) = 1 -> 위의 증명을 이용하면 gcd(p, a) = xp + ya = 1 양변에 b를 곱하면 xpb + yab = b 이고, p | xpb + yab 이다. (p | xpb는 자명하고, p | ..

『디버깅을 통해 배우는 리눅스 커널의 구조와 원리』 책을 보다 색다른 연결리스트들을 보게 되었다. 1. 꼬리 비우기형 보통 연결리스트 라고 하면 아래의 코드를 떠올렸다. struct list_head = { struct list_node *head; struct list_node *tail; }; new_node->next = NULL; list_head->tail->next = new_node;// 마지막 노드에 새로운 노드를 연결한다. list_head->tail = new_node;// 새로운 노드가 tail로 대체됨. 그런데 tail 맴버를 수정하면 다음과 같이 tail을 항상 비워두는 것으로 할 수 있다. (코드를 보면 알겠지만 실제로 빈 공간이 생기는건 아님) struct list_head =..