整数

合同式とは，わり算の余りのみに着目した等式のこと。

約数の個数は「素因数分解して」「それぞれの指数（右上の小さい数字）に1を足して」「全部かける」ことで計算できる。

正の整数 $a,b$ に対して，それらの最大公約数を $g$，最小公倍数を $l$ とおくと $ab=gl$

つまり，「最大公約数と最小公倍数の積」が「もとの二つの数の積」に等しい。

2つの正の整数について，両方ともを割り切る数（公約数）の中で一番大きいものを最大公約数と言います。

$x,y$ に関する不定方程式 $ax+by=c$ が整数解を持つ
$\iff$$c$ は $\mathrm{gcd}(a,b)$ の倍数

「平方数を $p$ で割った余りが $a$ になる場合がある」とき，$a$ は法 $p$ で平方剰余であると言う。

連続する２つの整数は互いに素である。

$2$ より大きな偶数は2つの素数の和で表せる。

$\dfrac{1}{2}$ のように，分子が $1$ である分数を単位分数と言います。

$\dfrac{1}{2}+\dfrac{1}{3}+\dfrac{1}{6}$ のように，分母が異なる単位分数の和のことをエジプト分数（エジプト式分数）と言います。

正の整数 $n$ に対し，$n$ 以下で $n$ と互いに素であるような正の整数の総和を $S(n)$ とする。

例えば，$S(1)=1，S(5)=1+2+3+4=10，S(6)=1+5=6$ である。

以下の問いに答えよ。

(1) $S(1024)$ を求めよ。

(2) $m=2021^{2021}$ とするとき，$\dfrac{S(m)}{m^2}$ の値を求めよ。

(3) $S(n)$ が偶数となるような $100$ 以下の正整数 $n$ の総和を求めよ。

連続する $n$ 個の整数の積は $n!$ の倍数である。

$n!$ に含まれる素因数 $p$ の数は以下の式で計算できる：

${\displaystyle \sum_{i=1}^{\infty}\left\lfloor \dfrac{n}{p^i} \right\rfloor}=\left\lfloor \dfrac{n}{p} \right\rfloor+\left\lfloor \dfrac{n}{p^2} \right\rfloor+\left\lfloor \dfrac{n}{p^3} \right\rfloor+\cdots$

ただし，$\lfloor x \rfloor$ は $x$ を超えない最大の整数を表す。

ピタゴラス数 とは，$a^2+b^2=c^2$ を満たす正の整数の組 $(a,b,c)$ のこと。

割り算の等式：$a=bq+r$ において，「$a$ と $b$ の最大公約数」＝「$b$ と $r$ の最大公約数」

ある自然数 $a$ が存在して

$a^{n}\not\equiv a \pmod{n}$

が成り立てば $n$ は合成数。

実数 $x$ に対して「$x$ の整数部分」を $\lfloor x\rfloor$ または $[x]$ と書くことが多い。

ただし「$x$ の整数部分」とは $n\leqq x <n+1$ を満たす整数 $n$ のこと。

例えば，$2.1$ の整数部分は $2$ なので $\lfloor 2.1\rfloor=2$

$\dfrac{1}{r}+\dfrac{1}{s}=1$ を満たす正の無理数 $r,s$ に対して以下が成立する。

全ての正の整数は以下の2つの数列のいずれかに必ず一回だけ登場する。

• $\lfloor mr\rfloor \:(m=1,2,3\cdots)$
• $\lfloor ns\rfloor \:(n=1,2,3\cdots)$

（自分自身を除いた）約数の総和＝相手となる正の整数のペアのことを友愛数と呼ぶ。

1. $r$ が有理数なら，$r$ の良い近似は有限個しかない
2. $r$ が無理数なら，$r$ の良い近似が無限個ある
3. $r$ が無理数なら，連分数展開により $r$ の良い近似が無限個得られる

$P(x)$ を $k$ 次多項式とする。

ある整数 $n$ が存在して $P(n),P(n+1),...,P(n+k)$ が整数なら，$P(x)$ は整数値多項式

$r$ が有理数であれば良い近似は有限個，$r$ が無理数であれば良い近似は無限個ある。

$2$ 以上の自然数 $n$ に対して，$n$ を割り切る素数の個数を $f(n)$ とする。例えば $n=120$ のとき，$120$ を割り切る素数は $2$ と $3$ と $5$ なので，$f(120) = 3$ である。不等式 $f(n) \geqq \dfrac{\sqrt{n}}{2}$ を満たす $2$ 以上の自然数 $n$ をすべて求めよ。

多くの状況で自然数の最初の桁（最高位）に現れる数は一様に分布しない。

具体的に $n \ (= 1,2, \dots , 9)$ の出てくる確率 $P_n$ は $$P_n = \log_{10} \dfrac{n+1}{n}$$ に近いことが多い。

等式 $x^2+y^2+z^2-3xyz = 0$ を満たす正の整数の組は無限個あることを証明せよ。

2つの奇数 $a,b$ に対して，$m = 11a+b$，$n = 3a +b$ とおく。次の1，2を証明せよ。

1. $m$ と $n$ の最大公約数は，$a$ と $b$ の最大公約数を $d$ として，$2d$，$4d$，$8d$ のいずれかである。
2. $m$，$n$ がともに平方数であることはない。

$n$ を自然数とする。実数 $x$ に対し，$x$ を超えない最大の整数を $[x]$ とし，$f(x) = x - [x]$ と定める。このとき，$1$ よりも大きく，かつ整数でないような実数 $x$ のうちで， $$\lim_{n \to \infty} f \left( \dfrac{1}{nf(\sqrt[n]{x})} \right) = \dfrac{1}{2}$$ を満たすものをすべて求めよ。

正の整数 $n$ に対し，$n$ の正の約数の個数を $d(n)$ とする。たとえば，$6$ の正の約数は $1, 2, 3 , 6$ の4個なので $d(6) = 4$ である。また， $$f(n) = \dfrac{d(n)}{\sqrt{n}}$$ とする。

(1) $f(2025)$ を求めよ。

(2) 素数 $p$ と正の整数 $k$ の組で $f(p^k) \leqq f(p^{k+1})$ を満たすものを求めよ。

(3) $f(n)$ の最大値と，そのときの $n$ を求めよ。

この問いでは，$0$ 以上の整数の2乗になる数を平方数と呼ぶ。$a$ を正の整数とし，$f_a (x) = x^2+x-a$ とおく。

1. $n$ を正の整数とする。$f_a (n)$ が平方数ならば，$n \leqq a$ であることを示せ。
2. $f_a (n)$ が平方数となる正の整数 $n$ の個数を $N_a$ とおく。次の条件 (i)，(ii) が同値であることを示せ。
   
   • (i) $N_a = 1$ である。
   • (ii) $4a+1$ は素数である。

• 自然数 $n$ に対して，$1$ から $n$ までの自然数の中で $n$ と互いに素なものの数を $\phi(n)$ と書き，オイラーの $\phi$ 関数と呼ぶことがある。

• $\phi$ 関数は $\phi(n)=n\displaystyle\prod_{i=1}^k\left(1-\dfrac{1}{p_i}\right)$という式で計算できる。ただし，$p_i$ は $n$ の素因数。

$p$ が素数で，$a$ が $p$ の倍数でない正の整数のとき $$a^{p-1}\equiv 1\pmod{p}$$

$a^4+4b^4\\=(a^2+2ab+2b^2)(a^2-2ab+2b^2)$

$2$ 以上の整数 $p$ について，$p$ が素数 $\iff (p-1)!\equiv -1 \pmod{p}$

$n_1$ と $n_2$ が互いに素なとき，

$$x\equiv a_1 \pmod{n_1}$$ $$x\equiv a_2 \pmod{n_2}$$

の両方を満たす整数 $x$ が $0$ 以上 $n_1n_2$ 未満の範囲にただ1つ存在する。

$n_i\: (i=1,\cdots, k)$ たちがどの2つも互いに素なとき，$k$ 本の連立合同式 $$x\equiv a_i \pmod{n_i}$$ を満たす $x$ が $0\leqq x <n_1n_2\cdots n_k$ の範囲にただ1つ存在する。

「$3$ 以上の素数 $p$」 と「$1$ 以上 $p$ 未満の整数 $r$」 が以下の性質を満たすとき，$r$ を法 $p$ に対する原始根と呼ぶ。

「$r,r^2,\dots,r^{p-2}$ のいずれもが $p$ で割って余り $1$ でない」

（また，$r=1$ は $p=2$ に対する原始根である，とする。）

$a$ が $p$ の平方剰余であるとき，

$\left(\dfrac{a}{p}\right)=1$ と定義します。

また，$a$ が $p$ の平方剰余でないとき，

$\left(\dfrac{a}{p}\right)=-1$ と定義します。

$2$ つの整数 $x,y$ を用いて $n=x^2+y^2$ と表される

$\iff n$ を素因数分解したときの $4k+3$ 型の素数の指数が全て偶数

Vieta jumping とは，ある文字について二次式であるような不定方程式を，解と係数の関係を用いて解くテクニックです。

$\mathrm{mod}\:p$ における $a$ の位数を $n$ とする。

$a^m\equiv 1\pmod{p}$ を満たすなら $m$ は $n$ の倍数である。

$p$ を素数とし，$p\neq 2,5$ とする。

$p$ を $5$ で割った余りが $1$ または $4$ なら，周期は $p-1$ の約数

$p$ を $5$ で割った余りが $2$ または $3$ なら，周期は $2(p+1)$ の約数

任意の無理数 $x$ と $0\leq a <b\leq 1$ を満たす任意の実数 $a, b$ に対して $a \leq \{nx\} \leq b$ を満たす自然数 $n$ が存在する。

$1$ から $n$ までの整数の中にある素数の数を $\pi(n)$ とおく。

$n$ が十分大きいとき，$\pi (n)\fallingdotseq \dfrac{n}{\log n}$

つまり，$\displaystyle\lim_{n\to\infty}\dfrac{\pi(n)\log n}{n}=1$

全ての正の整数は素数の積として（順番を除いて）一意に表せる。

ゼータ関数の非自明な零点の実部は $\dfrac{1}{2}$ である。

$n$ を3以上の整数とするとき，$x^n+y^n=z^n$ を満たす正の整数 $x,y,z$ の組は存在しない。

ナルシシスト数は有限個しかない

$2$ 以上の任意の整数 $n$ について，

$\displaystyle\sum_{d\mid n}\mu(d)=0$

正 $n$ 角形が定規とコンパスで作図可能 $\iff$

$n=2^Np_1\cdots p_k$ となる $0$ 以上の整数 $N$ と互いに異なるフェルマー素数 $p_1,\cdots,p_k$ が存在する。

任意の素数 $p$ と非負整数 $m,n$ に対して，

$${}_{m}\mathrm{C}_{n}\equiv\prod_{i=0}^k{}_{m_i}\mathrm{C}_{n_i}\pmod{p}$$

ただし，$m_km_{k-1}\cdots m_1m_0$ は $m$ の $p$ 進数表示，$n_kn_{k-1}\cdots n_1n_0$ は $n$ の $p$ 進数表示。

${}_m\mathrm{C}_n$ が素数 $p$ で割り切れる回数は $m-n$ と $n$ を $p$ 進数表示して足し算をしたときの繰り上がりの回数と等しい。

整数 $a,b$ を用いて $a+bi$ と表される複素数をガウス整数（複素整数）と呼ぶ。

すべての原始ピタゴラス数は，$\begin{pmatrix}3\\4\\5\end{pmatrix}$ に対して，3つの行列 $A,B,C$ のどれかをかける操作を何度か繰り返すことで作れる。ただし，

$A=\begin{pmatrix}1&-2&2\\2&-1&2\\2&-2&3\end{pmatrix}$ ，

$B=\begin{pmatrix}1&2&2\\2&1&2\\2&2&3\end{pmatrix}$ ，$C=\begin{pmatrix}-1&2&2\\-2&1&2\\-2&2&3\end{pmatrix}$

$a+b=c$ を満たす互いに素な自然数の組 $(a, b, c)$ であって，任意の $\epsilon > 0$ に対して， $$c > \text{rad} (abc)^{1+\epsilon}$$ を満たすものは有限個しか存在しない。

$0.$ のあとに正の整数を $1$ から小さい順に並べ続けた数

$0.12345678910111213\cdots$

をチャンパーノウン定数と言う。

$L_0=2,L_1=1,\\L_n=L_{n-1}+L_{n-2}\:(n\geq 2)$

で定まる数列 $\{L_n\}$ に現れる数をリュカ数と呼ぶ。

任意の正の整数は1通りの階乗進数として表される。

$1729$ は2つの立方数の和として2通りに表される最小の自然数である： $$1729=12^3+1^3=10^3+9^3$$ これを（ラマヌジャンの）タクシー数という。

$5$ 以上の任意の素数 $p$ に対して， $$\dfrac{1}{1}+\dfrac{1}{2}+\dfrac{1}{3}+\cdots +\dfrac{1}{p-1}$$ を既約分数で表したときの分子は $p^2$ の倍数。

$n$ を3以上の整数とするとき，$x^n+y^n=z^n$ を満たす正の整数 $x,y,z$ の組は存在しない。

$q \to 1$ で元の概念に一致するようにパラメーター $q$ を追加した概念を $q$-類似という。