| [ QuizWit ] in KIDS 글 쓴 이(By): khjeong (mathwhiz) 날 짜 (Date): 1998년04월07일(화) 15시56분58초 ROK 제 목(Title): [답] 0빠진 곱셈 오랜만에 KIDS에. 그냥 나가기 뭐해서... ----------------------------------------------------------- 먼저 n이 10과 서로 소임을 가정해도 좋습니다. 2와 5를 적당히 곱해서 마지막 0들을 버리면 되니까요. (n,10)이 서로 소이므로 Euler의 정리에 의하여, 10^\phi(n) = 1 (mod n) 이 됩니다. 즉, 10^e -1 = m*n 인 m, e가 존재하지요. n에 m을 곱하면, 10^e -1을 만들 수 있습니다. 따라서, n=999...99 (e 자리수) 인 경우만 살펴보면 됩니다. ** Comment : 집합 {9,99,999,9999,....}의 약수들의 집합이 10과 서로 소인 수들의 집합과 같댑니다. Euler 정리의 응용에 이런 것이 있는 줄은...... 이 때, m=111...11 (1이 e 개)을 곱하면 n*m=11...1088...89 (1은 e-1개, 8도 e-1개) 가 됩니다. 따라서, n=11...188...89 로 만들 수 있구요. 여기에 9를 곱하면, 10...070...01 이 됩니다. (0이 각각 e-1개 씩) 따라서, n=171 하나만 남았군요. 여기에 5848을 곱하면, 1000008 이 되므로, n=18이 되고, T_T 5를 곱해주면 9로 끝납니다. -- I owe you the sunlight in the morning. |