9
$\begingroup$

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!

$\endgroup$
3
  • 1
    $\begingroup$ I agree with $246$. If $n>123$ then $(n-123)$ divides $n!$ which implies that $(n-123)$ divides $123$. $\endgroup$
    – lulu
    Dec 29, 2023 at 9:16
  • 3
    $\begingroup$ It would be nice to add an attribution, if possible. This appears to be question #4 in the 2023 advent calendar here: mscroggs.co.uk $\endgroup$
    – mathmandan
    Dec 29, 2023 at 19:55
  • 2
    $\begingroup$ I've tried writing Python code, but the code craps out at 170 as the factorial term is too large for floating point numbers. ...why use floating point for an integer problem? use // and % $\endgroup$ Dec 30, 2023 at 10:49

4 Answers 4

12
$\begingroup$

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.

$\endgroup$
0
8
$\begingroup$

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$

$\endgroup$
6
$\begingroup$

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]
$\endgroup$
1
$\begingroup$

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$.

$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .