유리수의 순환마디 길이와 cyclic shift 증명 (feat.비둘기집 원리, 오일러 정리, 수학 주제탐구, 세특)
이 글에서는 분수를 순환소수(또는 유한소수)로
바꿀때 머릿속을 스치는 수학적 생각들을
모아서 설명하고 증명합니다.
1. 분수를 소수로 고치는 것은 나눗셈
예를들어, 1/7 을 바꾸려면
아래와 같은 계산을 해야 합니다.
첫 나눗셈에서 10 을 7 로 나눠서 몫이 1 이고
나머지가 3 입니다. 이어서 그 다음 나눗셈을 할 때
자리수 하나 내리고 나머지 3을 30으로 바꾸죠.
즉, 이런식으로, 7로 반복해서 나누는 동안
매 단계 10을 곱해주고 있고,
나머지가 순서대로 3,2,6,4,5,1 이 나오고 있습니다.
여기서 중요한것은
앞의 숫자는 뒤의 숫자를 하나로 결정합니다.
왜냐하면, 같은 나눗셈은 답이 동일하니까요.
그리고, 1이 나온 다음에는 반복이 됩니다.
(이 '1'의 의미는 1/7의 분자에 해당합니다.)
그러니 순환할 수 밖에 없죠.
만약, 2/7 을 계산했다면,
나머지가 2가 나올때 반복이 시작됩니다.
2. 순순환소수와 혼순환소수
위의 1/7 의 나눗셈에서 나머지 0 은 나오지 않습니다.
나머지가 0 이 나오면 유한소수가 됩니다.
만약, 기약분수의 분모의 소인수가
2, 5 만으로 구성되어 있으면
나눗셈 다음 단계가 될때,
직전 나머지에 10 을 곱해주는 것이 반복되므로
몇 번 진행하면 곧 분모의 배수가 되어서
나머지가 0 으로 나옵니다.
즉,유한소수가 됨을 알 수 있습니다.
예를들어, 분모가 20 이면
두 단계 진행하면 10 이 두 번 곱해지니
20 을 나누어 떨어지게 합니다.
즉, 자리내림 한 나눗셈 한 번마다
소인수 2, 5 한쌍을 처리할 수 있으니
소인수 2 또는 5 의 최대중복 갯수만큼 소숫점 아래
자리수가 생깁니다.
예를들어, 1/20 은 20에 소인수 2, 5 가 각각
두 개, 한 개가 있습니다.
첫번째 자리내림에서 2, 5 한쌍을 처리할 수 있고,
2 가 하나 더 남아 있으니 자리내림을 한 번 더 해야죠.
그래서 자리내림 두 번 하면 나눗셈이 완료됩니다.
즉, 0.05 가 되는데, 자리내림 두 번 했으니
소숫점 아래 두 자리까지 생기는 거죠.
다시말해서, 첫번째 나눗셈인 10 은 20 을 못 나누지만
두번째 나눗셈인 100 은 최초로 20 을 나눈다라는
의미입니다. 여기서, 100 은 10 의 2 제곱이니
이 2 가 소숫점아래 자리수 갯수입니다.
그리고,
분모가 2 또는 5와 다른 소인수가 섞여 있으면
혼순환소수가 되죠.
예를들어, 7/12 은
아래와 같이 변형할 수 있습니다.
따라서, 순순환소수 7/3 을
오른쪽으로 두 칸 밀어주게 되어서
이 됩니다.
여기서 '두 칸'의 이유는 12 의 소인수분해에서
소인수 2 가 2개 있기 때문입니다.
이것이 순환마디가 아닌 자리수의 갯수입니다.
3 순환마디 길이의 상한
1/7 처럼 나눗셈에서 나머지 0 이 안나오면
순환소수가 되죠.
만약 자리내림 후 나눗셈에서 나머지가 0 이 나오면
나눗셈이 종료되고 유한소수가 됩니다.
어떤 자연수를 7 로 나눈 나머지는
0, 1, 2, 3, 4, 5, 6
의 7개만 가능인데, 유한소수가 되는 0 을 제외하면
최대로 다양하게 나올수 있는 나머지가 6개 입니다.
따라서, 비둘기집 원리에 의해
7회 이상 나눗셈을 하면 같은 나머지가 나오고
앞의 나머지는 뒤의 나머지를 결정하므로
순환할 수 밖에 없죠.
따라서, 순환마디 길이의 상한은
분모보다 1 작습니다.
(여기서 '1' 은 나머지 0 을 의미합니다.)
1/m 이 순환소수일 때
순환마디는 m-1개 이하 이다
4. 순환마디의 길이는 φ(m)의 약수
1/7 의 나눗셈을 다시 보겠습니다.
첫번째 나머지 3은 10을 7로 나눈 나머지죠.
두번째 나머지 2는 자세히 보면
100을 7로 나눈 나머지입니다.
세번째 나머지 6은 1000을 7로 나눈 나머지이고
...
이런식으로 해서
10의 거듭제곱을 7로 나눴을때
최초로 나머지가 1이 될때까지가
순환마디가 됩니다. 즉,
인 최소의 자연수 n이 순환마디의 길이랍니다.
오일러 정리가 딱 떠오릅니다.
항등식인 이 식이 모양이 똑같네요!
(여기서 편의상 오일러 정리를 항등식이라 지칭합니다.)
n이 최솟값이므로 φ(7)>=n 이어야 합니다.
이제, φ(7)를 n으로 나눠보면
φ(7)=nq+r (0≤r<n)
이 됩니다. (나눗셈 정리)
이것을 오일러 정리에 대입하면
인데, n의 최소성에 의해
r=0 일 수밖에 없습니다.
그래서, φ(7)=nq 가 됩니다.
즉, 순환마디의 길이 n은 φ(7)의 약수입니다.
일반적으로, 7 대신 m을 써주면
1/m 을 순환소수로 썼을 때
순환마디의 길이는
φ(m)의 약수이다.
중요한 결과이니 암기해주세요.
φ(m)은 totient function 이라 하는데
m 이하의 자연수중에 m 과 서로소인 것의 개수를
의미합니다. 예를들어, 소수 p 라면 φ(p)=p-1 입니다.
따라서,
1/7 의 순환마디의 길이는 6의 약수인데
실제로도 6 입니다.
1/11 의 순환마디의 길이는 10의 약수인데
실제로는 2 입니다.
1/13 의 순환마디의 길이는 12의 약수인데
실제로는 6이구요,
1/17 의 순환마디의 길이는 16,
1/19 의 순환마디의 길이는 18,
1/23 의 순환마디의 길이는 22,
이런것들이 다 성립합니다.
5. 단위분수가 아닐때는?
1/m 이 아니라, k/m 인 경우는
(약분이 되면 새로운 나눗셈 계산이 되니 제외하고,)
약분이 안될때는 순환마디의 길이가 같습니다.
예를 들어, 1/7 의 경우,
에서 순환마디 앞의 숫자는 뒤의 숫자를 결정하고,
2/7 은 첫 나눗셈이 20÷7 로 시작하므로
0.2… 으로 시작하죠.
그러면 2→8→5→7→1→4 가 순서가 정해져 있으니
가 됩니다.
참고로 3/7 은 첫 나눗셈이 30÷7 로 시작하므로
첫 순환마디가 4 입니다. 이후 순환 순서는 동일하죠.
입니다. 이것을 cyclic shift 라고 해요.
참고로, cyclic shift 는 순환마디의 길이가
분모보다 1작을 때(꽉 찼을때)는 성립하지만
그 외에는 보장이 안됩니다,
예를들어, 1/7, 1/17 등은 순환마디가 꽉 찬
순환소수라서 cyclic shift 가 되고
1/11, 1/13 등은 순환마디가 꽉 차지 않아서 안됩니다.
이 대목은 관심있으시다면 각자 조금 더 연구해서
내용을 더 풍성하게 해보면 흥미로운실겁니다.
또는 아래와 같은 생각도 재미있습니다.
에서 양변에 100을 곱하면
이고, 여기서 양변에 14를 빼면
가 된답니다.
cyclic shift 가 작동되는 원리를 확인할 수 있죠.
순순환소수, 혼순환소수에 대해 좀 더 알고 싶으시다면
아래 링크를 참고해주세요~
재미있으셨나요?
혹시, 더 궁금하신 것이 있으시다면
아래 톡톡을 이용해 주세요