Really! composite

Fermat's Little theorem tells us $2^{p-1} \equiv 1 \mod p$ for all odd primes since no odd prime divides $2$ . Raising each side to the $k^{th}$ power, we have $2^{k(p-1)} \equiv 1^k \equiv 1 \mod p$ or $2^{k(p-1)}-1$ is divisible by $p$ for all odd primes. Hence, for $2^{n!}-1$ to be divisible by an odd prime $p$ , $n!$ must have a factor of $p-1$ .

Consider the set of all numbers which are 1 less than an odd prime $p<1000$ . Each of these numbers must divide $n!$ , so we proceed by factorizing them. Consulting the given list, the factorizations of the last numbers in this set are:

$997-1=996=2^2*3*83$

$991-1=990=2*3^2*5*11$

$983-1=982=2*491$

Since $491$ is prime, for no $m<491$ will $m!$ have a factor of $491$ , so we need $n\geq 491$ . Note, all numbers of this set except for $996$ , $990$ , and $983$ can be factorized into $2*q$ where $q<491$ . By definition of factorial, we can find factors of $2$ and $q$ in $491!$ . We can also find factors of $2^2$ , $3^2$ , $5$ , $11$ , and $83$ since they are each less than $491$ . Thus, $2^{491!}-1$ is divisible by all odd primes $p<1000$ .

We have shown that $n=491$ satisfies the conditions and is indeed the minimum, so our answer is $\boxed{491}$

From Fermat's Little Theorem, $a^{p-1}\equiv 1\pmod{p}$ where $p$ is a prime and $p\not |a$ .

Therefore, $2^{p-1}-1\equiv 0\pmod{p}$ or equivalently, $p|2^{p-1}-1$ .

Now all we need to find is the largest possible prime factor of $p-1$ , with $p$ any prime under $1000$ .

Since $983-1=982=2\times 491$ , and that $997-1=996=2^2\times3\times83$ , then $491$ must be the largest prime factor.

(This is because $2|p-1$ for $p\ne 2$ , so the highest prime you can get is $\dfrac{p-1}{2}$ .)

Therefore, the smallest $n$ can be is $\boxed{491}$ .

For all positive integers $k$ and $n$ , we define $\text{ord}_k(n)$ to be the smallest positive integer $m$ such that $k^m \equiv 1 \pmod{n}$ .

Claim If, for some positive integers $k, n, v$ , $k^v \equiv 1 \pmod{n}$ , then $v$ must be a multiple of $\text{ord}_k(n)$ .

Proof We write $v= a \times \text{ord}_k(n) + b$ for some non negative integers $a, b$ such that $0 \leq b \leq \text{ord}_k(n)-1$ by the division algorithm. Then, note that $k^v \equiv k^{ a \times \text{ord}_k(n) + b} \equiv \left ( k^{\text{ord}_k(n)} \right ) ^a \times k^b \pmod{n}$ $\equiv 1 \times k^b \equiv k^b \pmod{n}$ Since $k^v \equiv 1 \pmod{n}$ , we have $k^b \equiv 1 \pmod{n}$ . However, $b>0$ contradicts the minimality of $\text{ord}_k(n)$ , so we must have $b=0$ . This implies $\text{ord}_k(n) \mid v$ . QED
$$ Note that by Euler's theorem, for all co-prime $k$ and $n$ , $k^{\phi (n)} \equiv 1 \pmod{n}$ . From our first claim, it readily follows that $\phi (n)$ must be a multiple of $\text{ord}_k(n)$ .
$$ For all positive integers $m$ , let $f(m)$ denote the largest prime divisor of $\text{ord}_2(m)$ . $$ Consider any odd prime $p$ within the range $[1, 1000]$ . Since $2^{n!} \equiv 1 \pmod{p}$ , $n!$ must be a multiple of $\text{ord}_2(p)$ . For $n!$ to be a multiple of $\text{ord}_2(p)$ , it must be a multiple of its greatest prime factor, i.e it must be a multiple of $f(p)$ .
$$ From our previous observations, our answer will be simply the largest value of $f(p)$ , where $p$ ranges among all odd primes in the range $[1, 1000]$ . $$ Let's calculate $\text{ord}_2(983)$ . Note that $\phi (983) = 982= 2 \times 491$ , so we only have to check for $1$ , $2$ , $491$ , and $982$ . Checking it, we find out $\text{ord}_2(983)= 491$ . Again, since $491$ is prime, we have $f(983)= 491$ .

The primes larger than $983$ but less than $1000$ are $991$ and $997$ . Note that $991 \equiv 1 \pmod{3}$ , so $3 \mid 991-1$ , i.e. $3 \mid \phi(991)$ . It is now easy to see that $f(991) \leq \frac{991-1}{3}$ , which is obviously less than $491$ . Similarly, we find out that $f(997)<f(983)$ . For all smaller odd primes $p$ , note that $p-1$ is even, so $f(p)|p-1$ , and hence $f(p) \leq \frac{p-1}{2} < \frac{983-1}{2}= 491$ We thus conclude the maximum value of $f(p)$ is $491$ , which is attained for $p= 983$ . Our desired answer, hence, is $\boxed{491}$ .

When I saw this problem, I immediately thought of Fermat's Little Theorem. This theorem states that $a^{p-1} \equiv 1 \pmod p$ , for $a \in \mathbb{Z}^+$ and prime $p$ .

Thus, if $n!$ is divisible by $p - 1$ , then $2^{n!} \equiv 1 \pmod p$ since $2^{n!}$ is simply $(2^{p - 1})^k$ for some positive integer $k$ , thus it is still congruent to $1 \pmod p$ .

Immediately following, if $n!$ is divisible by every $p - 1$ for $p < 1000$ , then $2^{n!} - 1 \equiv 0 \pmod p$ , i.e. it is divisible by all $p < 1000$ .

So, we just have to find the largest prime in the prime factorization of any $p - 1$ for $p < 1000$ . Checking the largest few, we quickly come to $p - 1 = 982 = 2 \times 491$ . So, $491$ is the largest factor, thus $2^{491!} - 1$ is the smallest integer which is divisible by all odd primes $p < 1000. \blacksquare$

from Fermat's little theorem ,2^{p-1} is congruence 1 mod p from 983 is prime so 983 divide 2^{n!}-1 so 982 is divide n! so 491 is divide n! n>=491