자연수의 배수(배수 찾기)

자연수의 약수를 찾거나 소인수분해, 분수를 약분 또는 통분할 때 등의 경우, 우리는 배수를 이용한다. 간단한 수는 직관적으로도 찾을 수 있지만, 큰 수는 직관에만 의존할 수는 없다. 여러 번의 시행착오도 필요하고 시간도 많이 소모되며, 결국에는 계산기를 쓰는 일도 생긴다. 계산기 자체의 사용이 잘못된 것은 아니지만 우린 계산기보다는 필산으로 깔끔하게 답을 구하는 것을 선호한다.
배수의 특징을 알면 좀 더 수월한 계산을 할 수 있어서 몇 가지 정리한다. 이 글에서 사용할 기호와 공통적으로 사용하는 성질은 다음과 같다.

• \(a\mid b\quad\implies\)  \(a\)는 \(b\)를 나눌 수 있다. (\(b\)는 \(a\)의 배수이다. 또는 \(a\)는 \(b\)의 약수이다.)
  예) \(5\mid10,\quad 10\mid1000 \)

 

• \(a\nmid b\quad\implies\)  \(a\)는 \(b\)를 나눌 수 없다. (\(b\)는 \(a\)의 배수가 아니다. )
  예) \(2\nmid5,\quad 10\nmid108 \)

 

• \(p\mid n \quad\implies\quad n\equiv0\pmod p \quad\implies\quad n\mod p=0 \)
  예) \(2\mid8\quad\implies \quad 8\equiv0\pmod 2 \quad\implies\quad 8\mod 2=0 \)

 

• \((a + b) \mod p = ((a \mod p )\,+\, (b \mod p)) \mod p\)
  예)
  \(\eqalign{(8 + 11) \mod 3 &= ((8 \mod 3 )\,+\, (11 \mod 3)) \mod 3\\&=(2+2)\mod 3 \\&=1}\)

 

• \((a \times b) \mod p = ((a \mod p )\,\times\, (b \mod p)) \mod p\)
  예)
  \(\eqalign{(11 \times 4) \mod 3 &= ((11 \mod 3 )\,\times\, (4 \mod 3)) \mod 3\\&=(2\times1)\mod 3 \\&=2}\)

 

• \(\cdots\boxed{a_4}\boxed{a_3}\boxed{a_2}\boxed{a_1}=a_1 +a_2 \times10 +a_3 \times 10^2 +a_4 \times 10^3 +\cdots\)
  (단, \(a_n\)은 \(0,\,1,\,2,\,3,\,\cdots,\,9\))

 

---

#️⃣ \(2\mid n\quad\implies\) \(1\)의 자리의 숫자가 \(0,\,2,\,4,\,6,\,8\)인 경우

∵ \(\,2\mid10\)이므로

\(a_1+10\times(a_2+10\times a_3+ 10^2\times a_4 +\cdots) \equiv a_1\pmod2\)

 

#️⃣ \(3\mid n\quad\implies\)  각 자리의 숫자의 합이 \(3\)의 배수인 경우

∵ \(k=1,\,2,\,3,\,\cdots\)일 때, \(10^k \equiv 1\pmod3\)이므로

\(\eqalign{&a_1+ a_2 \times10 +a_3 \times 10^2 +a_4 \times 10^3 +\cdots\\ \equiv&a_1+ a_2 +a_3 +a_4 +\cdots\pmod3}\)

 

#️⃣ \(4\mid n\quad\implies\)  끝의 두 자릿수가 \(00\)이거나 \(4\)의 배수인 경우

∵ \(4\mid 100\)이므로

\(\eqalign{&a_1+a_2 \times 10 +100\times \left( a_3 +a_4 \times10 +\cdots \right)\\ \equiv&a_1+ a_2 \times10\pmod4}\) 

 

#️⃣ \(5\mid n\quad\implies\)  \(1\)의 자리의 숫자가 \(0\)이거나 \(5\)인 경우

∵ \(5\mid 10\)이므로

\(\eqalign{&a_1+10\times \left( a_2 +a_3 \times 10 + \cdots \right)\\ \equiv& a_1\pmod5}\)

 

#️⃣ \(6\mid n\quad\implies\) \(n\)은 각 자리의 숫자의 합이 \(3\)의 배수인 짝수

∵ \(2\mid6,\,\,3\mid6\)

 

#️⃣ \(7\mid n\)

⑴ 일의 자리의 숫자의 두 배와 나머지 수의 차가 \(0\) 또는 \(7\)의 배수인 경우

∵ \(n=a_1+10(a_2+10a_3+10^2a^4+10^3a^5+\cdots+10^{n}a_n)\)에서

\(A=a_2+10a_3+10^2a_4+10^3a_5+\cdots+10^{n}a_n\)이라 하면

\(n=10A+a_1\)이 \(7\)의 배수라면 \(2n=20A+2a_1\)도 \(7\)의 배수이다.

\(7\mid 21\)이므로 \(7\mid (21A-2n)\implies7\mid (A-2a_1)\)

⑵ 일의 자리부터 세 자리씩 끊어서 낮은 자릿수 그룹부터 \(+,\,-\)를 반복한 값이 \(7\)의 배수인 경우

∵ \(10^3+1\equiv0\pmod7,\,\,10^6\equiv1\pmod7\)이므로

\(\eqalign{n=&(a_1+10a_2+10^2a_3)+10^3(a_4+10a_5+10^2a_6)\\&+10^6(a_7+10a_8+10^2a_9)+10^9(a_{10}+10a_{11}+10^2a_{12})\\&+\cdots+10^{n-3}(a_{n-2}+10a_{n-1}+10^2a_n)}\)

\(\eqalign{n\equiv&(a_1+10a_2+10^2a_3)\\&+1001(a_4+10a_5+10^2a_6)-(a_4+10a_5+10^2a_6)\\&+(a_7+10a_8+10^2a_9)\\&+1001(a_{10}+10a_{11}+10^2a_{12})-(a_{10}+10a_{11}+10^2a_{12})+\cdots\pmod7\\\equiv&(a_1+10a_2+10^2a_3)\\&-(a_4+10a_5+10^2a_6)\\&+(a_7+10a_8+10^2a_9)\\&-(a_{10}+10a_{11}+10^2a_{12})+\cdots\pmod7}\)

⑶ 일의 자리의 숫자부터 \(1,\,3,\,2,\,-1,\,-3,\,-2\)를 곱하여 더한 수가 \(7\)의 배수인 경우

∵ \(10\equiv3\pmod7\)

   \(10^2\equiv2\pmod7\)

   \(10^3\equiv-1\pmod7\)

   \(10^4\equiv-3\pmod7\)

   \(10^5\equiv-2\pmod7\)

   \(10^6\equiv1\pmod7\)

   \(10^7\equiv3\pmod7\)

            ⁞

 

#️⃣ \(8\mid n\quad\implies\) 일의 자리부터 세 자릿수가 \(000\)이거나 \(8\)의 배수인 경우

∵ \(8\mid10^3\)

 

#️⃣ \(9\mid n\quad\implies\) 각 자리의 숫자의 합이 \(9\)의 배수인 경우

∵ \(k=1,2,3,\cdots\)일 때, \(10^k\equiv1\pmod9\)

 

#️⃣ \(10\mid n\quad\implies\)  \(1\)의 자리의 숫자가 \(0\)인 경우

∵ \(k=1,2,3,\cdots\)일 때, \(10\mid10^k\)

 

#️⃣ \(11\mid n\) 

⑴ 홀수 자리의 합과 짝수 자리의 합의 차가 \(0\)이거나 \(11\)의 배수인 경우

∵ \(10\equiv-1\pmod{11},\,\,10^2\equiv1\pmod{11}\)이므로

\(\eqalign{&a_1 +a_2 \times10 +a_3 \times 10^2 +a_4 \times 10^3 +\cdots\\\equiv&a_1-a_2+a_3-a_4+\cdots\pmod{11}}\)

⑵ 일의 자리의 숫자와 나머지 수의 차가 \(0\) 또는 \(11\)의 배수인 경우

∵ \(11A-(10A+a_1)\equiv A-a_1\pmod{11}\) (단, \(A\)는 \(7\)의 배수에서 ⑴과 같음.)

 

#️⃣ \(13\mid n\) 

⑴ 일의 자리의 숫자의 \(4\)배와 나머지 수의 합이 \(13\)의 배수인 경우

∵ \(53\equiv1\pmod{13}\)이므로

\(13A+(40A+4a_1)\equiv A+4a_1\pmod{13}\) (단, \(A\)는 \(7\)의 배수에서 ⑴과 같음.)

⑵ 일의 자리부터 세 자리씩 끊어서 낮은 자릿수 그룹부터 \(+,\,-\)를 반복한 값이 \(13\)의 배수인 경우

∵ \(13\mid1001,\,10^6\equiv1\pmod{13}\)

 

#️⃣ \(16\mid n\quad\implies\) 일의 자리부터 네 자릿수가 \(0000\)이거나 \(16\)의 배수인 경우

∵ \(16\mid10^4\)

 

#️⃣ \(17\mid n\quad\implies\) 일의 자리의 숫자의 \(5\)배와 나머지 수의 차가 \(0\) 또는 \(17\)의 배수인 경우

∵ \(18\equiv1\pmod{17},\,\,17\mid68\)이므로

\(68A-(50A+5a_1)\equiv A-5a_1\pmod{17}\) (단, \(A\)는 \(7\)의 배수에서 ⑴과 같음.)

 

#️⃣ \(19\mid n\quad\implies\) 일의 자리의 숫자의 \(2\)배와 나머지 수의 합이 \(19\)의 배수인 경우

∵ \(20\equiv1\pmod{19}\)이므로

\(20A+2a_1\equiv A+2a_1\pmod{19}\) (단, \(A\)는 \(7\)의 배수에서 ⑴과 같음.)

 

#️⃣ \(23\mid n\quad\implies\) 일의 자리의 숫자의 \(7\)배와 나머지 수의 합이 \(23\)의 배수인 경우

∵ \(70\equiv1\pmod{23}\)이므로

\((60A+6a_1)+(10A+a_1)\equiv A+7a_1\pmod{23}\) (단, \(A\)는 \(7\)의 배수에서 ⑴과 같음.)

 

#️⃣ \(27\mid n\quad\implies\) 일의 자리부터 세 자리씩 끊은 숫자들을 모두 더한 수가 \(27\)의 배수인 경우

∵ \(10^3\equiv1\pmod{27}\)이므로

\(n\equiv(a_1+10a_2+10^2a_3)+(a_4+10a_5+10^2a_6)+(a_7+10a_8+10^2a_9)+\cdots\pmod{27}\)

 

#️⃣ \(29\mid n\quad\implies\) 일의 자리의 숫자의 \(3\)배와 나머지 수의 합이 \(29\)의 배수인 경우

∵ \(30\equiv1\pmod{29}\)이므로

\(30A+3a_1\equiv A+3a_1\pmod{29}\) (단, \(A\)는 \(7\)의 배수에서 ⑴과 같음.)

 

#️⃣ \(31\mid n\quad\implies\) 일의 자리의 숫자의 \(3\)배와 나머지 수의 차가 \(0\) 또는 \(31\)의 배수인 경우

∵ \(31A-(30A+3a_1)\equiv A-3a_1\pmod{31}\) (단, \(A\)는 \(7\)의 배수에서 ⑴과 같음.)

 

#️⃣ \(37\mid n\quad\implies\) 일의 자리부터 세 자리씩 끊은 숫자들을 모두 더한 수가 \(37\)의 배수인 경우

∵ \(10^3\equiv1\pmod{37}\)이므로
\(n\equiv(a_1+10a_2+10^2a_3)+(a_4+10a_5+10^2a_6)+(a_7+10a_8+10^2a_9)+\cdots\pmod{37}\)