Question

不能表示为 $42$ 的正整数倍与一个正合数之和的最大正整数是多少？

What is the largest positive integer that is not the sum of a positive integral multiple of $42$ and a positive composite integer?

答案

答案：215

知识点：模运算因数极端原理

难度评级：2110

小提示：

对模 $42$ 的每个余数，找出该余数类中最小的正合数

For each residue modulo $42$ , find the smallest positive composite integer in that residue

大提示：

一个余数类中一旦有一个数可以表示，该余数类中比它大 $42$ 的每个数都可以表示

Once one number in a residue class is representable, every number $42$ larger in that class is representable

解答：

余数类 $r\pmod {42}$ 中的数，只要比该类最小的正合数大 $42$ 的正整数倍，就可以表示。若余数 $r$ 本身是合数，它就给出第一个这样的数。对其余余数，可以选取如下第一个合数： $\begin{aligned}&0:42,\ 1:85,\ 2:44,\\&3:45,\ 5:215,\ 7:49,\\&11:95,\ 13:55,\ 17:143,\\&19:145,\ 23:65,\ 29:155,\\&31:115,\ 37:121,\ 41:125\end{aligned}\text{。}$ 其中最大的数是 $215$ ，而 $215-42$ 、 $215-84$ 、 $215-126$ 、 $215-168$ 和 $215-210$ 都是素数。因此 $215$ 不能表示，而每个更大的整数都可以表示。

A number in residue class $r\pmod {42}$ is representable once it exceeds the first positive composite in that class by a positive multiple of $42.$ Composite residues $r$ themselves supply that first value. For the remaining residues, suitable first composites are $\begin{aligned}&0:42,\ 1:85,\ 2:44,\\&3:45,\ 5:215,\ 7:49,\\&11:95,\ 13:55,\ 17:143,\\&19:145,\ 23:65,\ 29:155,\\&31:115,\ 37:121,\ 41:125.\end{aligned}$ The largest entry is $215,$ and $215-42,$ $215-84,$ $215-126,$ $215-168,$ and $215-210$ are all prime. Hence $215$ is not representable, while every larger integer is.

1995 AIME 第 10 题

答案：215

难度评级：2110

小提示：

大提示：

解答：

其他年份的第 10 题