2010년 10월 30일 토요일

19의 배수 판정법에 대하여..

학교에서 Number Theory 배우다가 Division Test라는 게 있더라.

거긴 1001=7*11*13까지만 나와있었는데..

순간 생각난 게 있어서 한번 써본다.

일단 10^k승의 least nonnegative residue(modulo 19)를 k로 나타내보면 어떻게 나타낼수 있을까.. 하는 것에 대해서 생각해보니까...

일반항은 못구해도 간단한 방법으로 점화식은 가능할 듯 싶다.

뭐 10의 k승이라고 할 것도 없이.

x가 mod 19일때 a와 컨그런스하다고 하다면,

a가 even이면 2k꼴로 나타낼 수 있으며

10x는 20k와 mod 19일때 컨그런스하고, 곧 20k는 k와 컨그런스하다.

한마디로, x 가 2k와 컨그런스하면, 10x는 k와 컨그런스 하다는 이야기.

a가 odd면 a+19는 even이며, 위와 같은 방식으로 할 수 있다.

이걸 이용해보면 10^0, 10^1, 10^2... 10^k까지의 mod 19의 absolute value가 least한 residue를 바로바로 구할 수 있다.

간단히 1, -9, 5, -7, 6, 3...로, 매우 간결한 알고리즘을 이용해서 구할 수 있다.
그 수들을 A_0 = 1, A_1 = -9, A_2= 5 등등으로 나타내서 10^k의 absolute value가 least한 residue를 A_k로 하고.

배수를 판정해야되는 k+1자리 10진수가 (N_k N_k-1 N_k-2 ... N_0)_(10)이 있으면, 그 수는

N_k * 10^k + N_k-1 * 10^k-1 + ... + N_0 * 10^0 = 은
k
시그마 N_i * A_i 로 나타낼 수 있다.
i=0

더 간단히 말하자면, 자리수가 있을때 저 A_k를 손쉽게 전개해서, 각 자리수와 대응해서 곱한다면(마치 벡터처럼) 한 자리 수 * 한 자리 수의 합으로 나타낼 수 있으므로 훨씬 쉽게 구할 수 있다.

현재 19의 배수 판정법이라는 것도 위와 비슷한 이치다. 원리상으론 굉장히 간단하게, ABCDE가 있으면 ABCD+2E와 mod 19일때 컨그런스하기 때문에 한 자리씩 줄인다는 이야기인데..

자릿수가 세~네자리면 굉장히 유용한 방법이라고 생각한다. 하지만 10자리가 넘는다면(아 솔까말 열자리 넘으면 손으로 안하겠제..) 이번에 제안한 방법도 방법이 되지 않을까.

이걸 응용한 방법도 생각해 봤다.

사실 17의 배수 판정법도 금방 응용할 수 있을텐데.

x가 mod 17일때 even인 a(=2k)라고 하면, 10x는 20k, 곧 3k이므로..

뭐 특별한 경우에는, 예를 들자면 16이 mod 17일때 16이니까.

160은 24, 1600은 36, 16000은 54, 160000은 81이 되겠다.

근데 사실 응용하긴 힘들 것 같고.. 그럴 수 있다고만 보면 되겠다.

에고, 피곤하다.

댓글 없음:

댓글 쓰기