10의 제곱수와 모듈로 9 연산의 활용, 디지털 루트(자릿수근), repeated digital sum

디지털 루트를 계산할 때 % 9 연산을 사용하는 것은 숫자의 '모듈로 9'에 대한 성질과 관련이 있다.
숫자의 '각 자리수의 합'과 '모듈로 9' 연산 간의 관계를 살펴보자.

모듈로 연산은 덧셈과 곱셈에 대해 분배 법칙을 만족한다. 즉, (a + b) % n = ((a % n) + (b % n)) % n과 (a * b) % n = ((a % n) * (b % n)) % n이다.

각 자리수의 합 = 해당 숫자 모듈로 9
어떤 숫자를 10진법으로 표현했을 때, 해당 수의 디지털 루트는 해당 수를 9로 나눈 나머지와 같다. 예를 들어, 숫자 467은 4 * 100 + 6 * 10 + 7과 같이 표현할 수 있다. 이 때, 100과 10은 (mod 9) 연산에 의해 1이 되므로  (즉, 100 % 9 = 10 % 9 = 1), 467 % 9는 (4 * 100 + 6 * 10 + 7) % 9 은 (4 + 6 + 7) % 9 과 같아진다. 이어서 두자리 수(4+6+7=17) 이므로 계속해서 연산하면 (1 * 10 + 7) % 9 = 8 이므로 467의 디지털 루트는 8이다.
 
해당과정을 모듈로 곱셋 분배 법칙을 생략하고 467 % 9 = 8 로 간단하게 구할 수  있다.

**mod 9 연산의 결과가 0인 경우, 디지털 루트는 9로 정의된다(예: 18의 디지털 루트는 1 + 8 = 9) 

 

 
 (10의 제곱수) mod 9 = 1이 되는 성질로 % 9 연산을 사용하여 디지털 루트를 구하는 것이 가능하다. 이 방법은 특히 큰 숫자에 대해 계산할 때 유용하며, 코드의 효율성과 성능을 높이는 데 도움이 될 수 있다.

 

부연 설명 추가 

• 10 ≡ 1 (mod 9)이므로,
  10^k≡1^k≡1 (mod 9)
• 아래와 같이 공식화 할 수 있다. (9를 b - 1로 바꾸면, 진수가 b인 진법으로 일반화할 수 있음)

 
 
 
 
 
참고 문제 
https://www.acmicpc.net/problem/6378

6378번: 디지털 루트

https://www.hackerrank.com/challenges/recursive-digit-sum/problem

Recursive Digit Sum | HackerRank

 
참고 자료

https://ko.wikipedia.org/wiki/%EC%9E%90%EB%A6%BF%EC%88%98%EA%B7%BC
https://www.quora.com/How-would-I-prove-that-every-positive-integer-is-congruent-to-the-sum-of-its-base-10-digits-modulo-9

자릿수근 - 위키백과, 우리 모두의 백과사전

 

How would I prove that every positive integer is congruent to the sum of its (base-10) digits modulo 9?