一个正整数,除以6余1,除以7余2,除以8余3,除以9余4求满足这个条件的最小的正整数
时间: 2023-05-29 14:03:17 浏览: 186
给“余”猜数,由用户事先想好一个大于0的正整数x,将它分别除以某几个正整数得到余数,将这几个数与余数一并告诉计算机,计算机能马上猜出满足条件的最小正整数,如果条件矛盾,输出无解。
4星 · 用户满意度95%
根据题意可以列出如下方程组:
$$\begin{cases}n \equiv 1 \pmod{6} \\n \equiv 2 \pmod{7} \\n \equiv 3 \pmod{8} \\n \equiv 4 \pmod{9}\end{cases}$$
为了方便计算,我们可以将这个方程组转化为一个同余方程,即:
$$n \equiv a_i \pmod{m_i}$$
其中 $a_1=1,a_2=2,a_3=3,a_4=4,m_1=6,m_2=7,m_3=8,m_4=9$。
我们可以使用中国剩余定理来求解这个同余方程,具体步骤如下:
1. 求出 $M=m_1m_2m_3m_4=1512$。
2. 求出 $M_i=M/m_i$,即 $M_1=252,M_2=216,M_3=189,M_4=168$。
3. 求出 $t_i$,满足 $M_it_i \equiv 1 \pmod{m_i}$。可以使用扩展欧几里得算法来求解,也可以通过观察发现 $M_it_i$ 恰好是 $m_i$ 的一个余数,即:
$$\begin{aligned}M_1t_1 &\equiv 1 \pmod{6} \Rightarrow t_1 \equiv 2 \pmod{6} \\M_2t_2 &\equiv 1 \pmod{7} \Rightarrow t_2 \equiv 4 \pmod{7} \\M_3t_3 &\equiv 1 \pmod{8} \Rightarrow t_3 \equiv 5 \pmod{8} \\M_4t_4 &\equiv 1 \pmod{9} \Rightarrow t_4 \equiv 5 \pmod{9} \end{aligned}$$
4. 将 $n=\sum_{i=1}^4a_iM_it_i$ 带入同余方程,即可得到 $n$ 的一个最小正整数解:
$$n \equiv 1 \times 252 \times 2 + 2 \times 216 \times 4 + 3 \times 189 \times 5 + 4 \times 168 \times 5 \equiv 881 \pmod{1512}$$
因此,满足条件的最小正整数为 $881$。
阅读全文