Lucas 定理

设 $p$ 素数, $m$ 和 $n$ 是非负整数. 则

\[
\binom{m}{n}\equiv\prod_{i=0}^{k}\binom{m_i}{n_i}\pmod p
\]

其中

\[
\begin{aligned}
m&=m_k p^k+m_{k-1}p^{k-1}+\cdots+m_1 p+m_0,\\
n&=n_k p^k+n_{k-1}p^{k-1}+\cdots+n_1 p+n_0,\\
\end{aligned}
\]

约定 $\binom{m}{n}=0$, 如果 $m < n$.

一个直接推论是 $p|\binom{m}{n}$ 当且仅当存在 i, 使得 $n_i > m_i$.

例子: 设 $p$ 是素数, $m\geqslant 1$, $0\leqslant k\leqslant p-1$, 证明

\[
\binom{mp+k}{p}\equiv m\pmod p
\]

References:

https://en.wikipedia.org/wiki/Lucas%27_theorem

正整数 $a,b,c$ 都是两位数, 且 $a,b$ 的个位数字分别是 7 和 5. $c$ 的十位数字是 1. 如果它们满足

\[
a\times b+c=2005,
\]

求这三个数的和.

一自然数末两位数字为 17, 各位数字和为 17, 且能被 17 整除. 求满足条件的最小五位数.

用数学语言写的话, 就是设 $n$ 满足

\[
\begin{cases}
n=100m+17,\\
\text{digitSum}(n)=17,\\
n\equiv 0\pmod {17}
\end{cases}
\]

求满足条件的最小的五位数 $n$.

求

\[
(1!+2!+3!+\cdots+100!)^{1!+2!+3!+\cdots+100!}
\]

的个位数字.

[Remark] 这种问题都是装的很难的样子, 其实没有太大意义.

我们只要知道 $n!$ 当 $n\geqslant 5$ 时, 乘积中就包含了 5 和 2, 因此 $n!$ 就是 10 的倍数.

1. 在 1 到 2013 这些正整数中, 有多少个数乘以 48 后是完全平方数?

2. 某自然数加 10 和减 10 所得的数都是完全平方数, 求这个自然数.

3. 求能被 180 整除的最小的完全平方数.

$n!+7=m^2$, 求 $(n,m)$.

[Hint] 模 4 即可.

注意如果方程换成

\[
n!+1=m^2,
\]

则就非常难了, 目前还是 open problem. 见问题1711

立方数指一个整数的三次方 $n^3$. 这里我们仅考虑非负整数.

下面是 $n=0,1,2,\ldots,999$ 的三次方(以十进制表示)

(0, 1, 8, 27, 64, 125, 216, 343, 512, 729, 1000, 1331, 1728, 2197, 2744, 
3375, 4096, 4913, 5832, 6859, 8000, 9261, 10648, 12167, 13824, 15625, 17576, 
19683, 21952, 24389, 27000, 29791, 32768, 35937, 39304, 42875, 46656, 50653, 
54872, 59319, 64000, 68921, 74088, 79507, 85184, 91125, 97336, 103823, 110592, 
117649, 125000, 132651, 140608, 148877, 157464, 166375, 175616, 185193, 195112,
205379, 216000, 226981, 238328, 250047, 262144, 274625, 287496, 300763, 314432,
328509, 343000, 357911, 373248, 389017, 405224, 421875, 438976, 456533, 474552,
493039, 512000, 531441, 551368, 571787, 592704, 614125, 636056, 658503, 681472,
704969, 729000, 753571, 778688, 804357, 830584, 857375, 884736, 912673, 941192,
970299)

请问 $n^3$ 是否有某些特征? 并请证明.

1. 末尾数字以 0,1,8,7,4,5,6,3,2,9 循环出现. 这个很好理解, 只需考虑模 10

\[
(10m+k)^3\equiv k^3\pmod {10}
\]

Program:

软件: ARIBAS

代码:

function cubevec(len: integer): array;
var 
   vec: array[len];
    i: integer;
begin
    for i:=0 to len-1 do
        vec[i]:= i**3;
    end;
    return vec;
end.

判断 $4^{10}+2$ 是否是完全平方数.

[Hint]

若记 $\text{lastdigit}(m)$ 为整数 $m$ 在十进制下的末尾数字, 则容易证明,

\[
\text{lastdigit}(4^{n})=\begin{cases}
4, & \text{当}\ n\ \text{是奇数时},\\
6, & \text{当}\ n\ \text{是偶数时}.\\
\end{cases}
\] 

因此, 这里 $4^{10}+2$ 末尾数字是 8, 而完全平方数的末尾数字只可能是 $0,1,4,9,6,5$. 故 $4^{10}+2$ 不是完全平方数.

完全平方数指一个整数的平方. 

如 0,1,2,3,...,99 的平方是

0, 1, 4, 9, 16, 25, 36, 49, 64, 81, 100, 121, 144, 169, 196, 225, 256, 289,
324, 361, 400, 441, 484, 529, 576, 625, 676, 729, 784, 841, 900, 961, 1024, 
1089, 1156, 1225, 1296, 1369, 1444, 1521, 1600, 1681, 1764, 1849, 1936, 2025, 
2116, 2209, 2304, 2401, 2500, 2601, 2704, 2809, 2916, 3025, 3136, 3249, 3364, 
3481, 3600, 3721, 3844, 3969, 4096, 4225, 4356, 4489, 4624, 4761, 4900, 5041, 
5184, 5329, 5476, 5625, 5776, 5929, 6084, 6241, 6400, 6561, 6724, 6889, 7056, 
7225, 7396, 7569, 7744, 7921, 8100, 8281, 8464, 8649, 8836, 9025, 9216, 9409, 
9604, 9801

其末尾数字只可能取下面的值: 0, 1, 4, 9, 6, 5.

我们注意到上面这些数末尾数字的变化规律是 0, 1, 4, 9, 6, 5; 6, 9, 4, 1, 0, 1, 4, 9, 6, 5, ... . 即

0, 1, 4, 9, 6, 5;

------- > ------
_______________|
|_______________

请证明这个规律.

设 $p$ 是素数, 所谓的 $p$-adic 整数(p-adic integer) 是指形如下面的数, 

\[
\sum_{k=m}^{\infty}a_k p^k
\]

其中 $m\geqslant 0$, $a_i\in\{0,1,2,\ldots,p-1\}$. 也就是说 $p$-adic 整数实际上相当于 $p$ 进制的整数. 通常我们记作 

\[
(a_i)=\overline{\cdots a_i\cdots a_3 a_2 a_1 a_0}.
\]

两个 $p$-adic 整数可以相加, 法则与通常的十进制加法是类似的, 要考虑进位.

也可以作减法, 不过要注意的是, 这里的负 $p$-adic 整数是没有负号的, 它的特点是除了有限位以外, 所有的位都是 $p-1$.