代数(1) 合同式、整数

合同式

整数 $a$, $b$, $m$ において $a$ を $m$ で割った余りと $b$ を $m$ で割った余りが等しい時（$a-b$ が $m$ で割れるとき）、$$a\equiv b\pmod m$$とあらわす。たとえば、$$8\equiv 3 \pmod 5,\quad 6\equiv 11 \pmod 5,\quad -4\equiv 3 \pmod 7$$などとなる。合同式の足し算引き算掛け算は通常と同様にできる。(→P.94参照)

例題

次のうち正しいものを選べ。

(ア) $5\equiv7\pmod 2$

(イ) $4\equiv13\pmod 6$

(ウ) $13\equiv37\pmod 6$

(エ) $79\equiv34\pmod 5$

(オ) $18\equiv27\pmod 5$

問題

1

$1!+2!+3!+4!+5!+6!+7!+8!+9!$ の一の位を求めよ。

2

(JJMO2005予選-2) $197$ を割っても $290$ を割っても $11$ 余る正の整数をすべて求めよ。

3

$2004!$ の末尾に並ぶ $0$ の個数を求めよ。

4

整数 $x$, $y$ が $5\mid x+9y$ を満たすならば、$5\mid 8x+7y$ が成り立つことを示せ。

5

$a$, $b$, $c$ を連続する自然数とするとき、$(a+b+c) ^ 3-3(a ^ 3+b ^ 3+c ^ 3)$ は $108$ で割り切れることを示せ。

6

$1,11,111,\dots,11\cdots1$ (2003 桁) の 2003 この数のうち、少なくとも一つは $2003$ の倍数であることを示せ。

解答

例題

(ア), (ウ), (エ)

問題 1

【方針】$\bmod{10}$ で考えればよい。

【解答】$1!\equiv1\pmod{10}$, $2!\equiv2\pmod{10}$, $3!\equiv6\pmod{10}$, $4!\equiv4\pmod{10}$, $5!,6!,7!,8!,9!\equiv0\pmod{10}$ であるから、$$1!+2!+3!+4!+5!+6!+7!+8!+9!\equiv1+2+6+4\equiv3\pmod{10}$$ より、求める値は $3$.

問題 2

【解答】求める整数を $p$ とすると、問題文より $$197\equiv11\pmod p,\quad 290\equiv11\pmod p$$ であるから、$$186\equiv279\equiv0\pmod p\cdots\text{①}.$$ $197$ を $p$ で割った余りが $11$ であるから、$p>11$. ①を満たす整数のうち、$p>11$ であるような整数は $31$ と $93$ のみであり、この 2 数はともに題意を満たすから、求める数は $31$, $93$ である.

問題 3

【方針】$2004!$ が何回 $10$ で割り切れるか数えればよい。$10=2\times5$ であるから、$2004!$ の素因数分解に現れる $2$, $5$ の素数をそれぞれ数えれば求められる。

配布用問題

1

$p$ が $5$ 以上の整数のとき、$p ^ 2-1$ は $24$ で割り切れることを示せ。

2

$21,221,2221,22221,\dots$ の中には平方数がないことを示せ。

3

(JJMO2003予選問5改題) $1$ 以上 $2010$ 以下の整数であって、正の約数を偶数個持つものの個数を求めよ。

4

(JMO1991予選問1) $A=999..9$ (81 桁すべて $9$) とする。$A ^ 2$ の各桁の数字の和を求めよ。

5

$100$ 以下の正の整数の組 $(a,b)$ であって $b<a$ を満たし、$\dfrac{a}{b}$ と $\dfrac{a+1}{b+1}$ がともに整数となるようなものはいくつあるか。

6

$2 ^ {2004}$ を $1,2,3,\dots,2 ^ {2004}$ で割ってそれぞれ商と余りを求める。このとき、商としてあらわれる整数は何種類あるか。