Solving a problem involving a factorial

Question

Need some guidance on a problem I'm trying to solve:

If n is $1, 2, 4$, or $6$ then $\frac{(n!-3)}{(n-3)}$ is an integer. The largest of these numbers is $6$. What is the largest possible value of n for which $\frac{(n!-123)}{(n-123)}$ is an integer?

I'm totally stumped on this. I tried brute force by substituting the '$123$' (let's call that $p$) with smaller numbers less than $10$ to see if there's a discernible pattern.

It seems to be the case that with smaller values of $p$, the equation is an integer when $n = 2p,$ which would suggest the answer is $246$. However I'm told this is incorrect.

I've also tried writing some Python code to test $n$ up to $999$, but the code craps out at $170$ as the factorial term is too large for floating point numbers.

I strongly believe there's a better way of solving this than brute force...but I'm stumped on which way to go here. I've been toying with 'if the expression is an integer then $(n!-123) = k(n-123)$ for some integer $k$, but this is getting me nowhere. I still don't know how to handle factorials algebraically.

Any pointers greatly appreciated!

Answer 1

So we want to find the biggest $k$, where

$$\frac{n!-123}{n-123} = k$$

Now, we can rearrange this to yield

$$n!-123 =k(n-123)$$

Now if $n > 123$ (we can do this since we are seeking for the largest $n$, and all smaller cases won't matter if we find a larger one), then

$$n!-123 \equiv n(n-1)\cdots(n-123)\cdots(3)(2)(1) -123 \equiv -123 \equiv 0 \pmod {n-123}$$

Thus, $$-123 \equiv 0 \pmod{n-123}$$

And the only way for this to work is if $123$ is a multiple of $n-123$. To find the largest $n$, we will need to take the largest factor. Thus, $123 = n-123$, and thus $n=246$ is the largest $n$.

In fact, the largest $K$ for $$\frac{N\hspace{0.5mm} ! -p}{N-p} = K$$ is actually $2p$, if we repeat the process above for all values.

Answer 2

Hint:

Let $m=n-123$

$$\dfrac{(m+123)!-123}m=\prod_{r=1}^{123}(m+r)\cdot\prod_{t=1}^{m-1}t-\dfrac{123}m$$

So, we need $m|123$

Answer 3

Other answers already give a simple math argument proving that the maximum is 246.

I'd like to address this:

I've also tried writing some Python code to test up to 999, but the code craps out at 170 as the factorial term is too large for floating point numbers.

You're only interested in knowing whether $\frac{n!-123}{n-123}$ is an integer; in other words, you're only interested in knowing whether $n!-123$ is divisible by $n-123$; yet in other words, you're only interested in knowing whether $n!-123 \equiv 0 \mod {(n-123)}$.

Therefore, you don't need to compute $n!$ in python; you only need to compute $n! \mod {(n-123)}$. This doesn't require big integers, because modular arithmetic works well with multiplication.

With math symbols, we say that if: \begin{align*} a & \equiv a' \mod{m} \\ b & \equiv b' \mod{m} \\ \end{align*} then: $$a \times b \equiv a' \times b' \mod{m}$$

In python, this translates to:

(a * b) % m == ((a % m) * (b % m)) % m

Which means we never need to care about integers larger than $m$ in order to compute a product modulo $m$.

def fact_mod(n, m):
    f = 1
    for k in range(n+1):
        f = (f * (k % m)) % m
    return f

def gen_n_123(N=1000):
    for n in range(N):
        if n != 123 and (fact_mod(n, n-123) - 123) % (n - 123) == 0:
            yield n

def main():
    print(list(gen_n_123()))

if __name__ == '__main__':
    main()

Output:

[0, 82, 120, 122, 124, 126, 164, 246]

Answer 4

When $n-123>0$, we have $n-123\mid n!$. Therefore we must have $n-123\mid 123$.

Thus $n=2\cdot 123 = 246$ is the largest value for $n$.