2

How to prove or disprove that there exists an integer number $x$ s.t. $x>0,\,x < 4\cdot99!$ and $x(x+1)$ is divisible by $100!$?

Git Gud
  • 31,356
user64494
  • 5,811
  • 3
    Have you tried anything? Any ideas? – naslundx Feb 28 '14 at 15:32
  • I have unsuccessfully thought about that. – user64494 Feb 28 '14 at 15:35
  • 4
    I am not the one who downvoted. However, you should be aware that the criteria for downvoting are "this question does not show any research effort" or "this question is unclear or not useful". Indeed, it is easy to interpret the terseness of your question as showing a lack of effort on your part. – Ben Grossmann Feb 28 '14 at 15:45
  • As far as I know that,the problem is very hard. The number 100! is too big for enumeration of possibilities with Maple. – user64494 Feb 28 '14 at 15:48
  • 2
    @Omn Correction: some users downvote for said reasons. Many, don't. Some people never downvote for any reason. There are no universal criteria for voting. It is a highly subjective decision, and often poorly made. As such, it is usually best to ignore votes. – Bill Dubuque Feb 28 '14 at 15:49
  • 1
    @Bill Dubuque: hover your mouse over the downvote arrow. Anyway to the question, I'm almost sure there is such integer, I can't prove it yet though. – user2345215 Feb 28 '14 at 15:57
  • You downvote a problem authored by S. Konyagin. Don't laugh people – user64494 Feb 28 '14 at 16:09
  • 1
    @user2345215 Which does not contradict what I wrote. The MSE site behaves quite differently than SE "recommendations" in many ways. And the randomness and incomprehensibilty of votes is a frequent topic on meta. My recommendation is to completely ignore votes and instead concentrate on sharing mathematical knowledge, which is the primary purpose of this site. – Bill Dubuque Feb 28 '14 at 16:12
  • Hint: x and $x+1$ are always coprime. So if p divides x, then $p^\max$ divides x, where $\max$ is the greatest power of p which divides $100!$. So: how many times does a prime enter into $100!$ ? – Lucian Feb 28 '14 at 16:37
  • 3
    $$x=\frac{100!}{6197}91$$ By modular arithmetic we can verify that $x+1$ is inedeed divisible by $6197$(and it is obviously $<499!$). – chubakueno Feb 28 '14 at 17:35
  • @chubakueno: Can you kindly transform your comment to an answer, explaining how you arrive at $x?$ – user64494 Feb 28 '14 at 17:51
  • @chubakueno: Dammit! I was trying the same thing but I didn't realize I could multiply it if it's much lower to get the result! – user2345215 Feb 28 '14 at 17:54
  • @user64494 Done! – chubakueno Feb 28 '14 at 18:19
  • @user2345215 It happens sometimes :) I realized that exculding only one prime I wasn't going to get too far, so I thought about including two primes and hopefully expect for solutions (having $pq$ different possible soltions for $k$, the probability of finding a $k$ such that $25k<pq$ was kind of low, but having $10$ primes to choose from, $\binom{10}{2}=45$ tries it seemed like enough assuming that solutions are uniformly distributed).Finally, I got it. – chubakueno Feb 28 '14 at 18:24

1 Answers1

4

$$x=\frac{100!}{61\times97}\times91$$ By modular arithmetic we can verify that $x+1$ is indeed divisible by $61*97$(and it is obviously $<4\times 99!$).

How it was done: I arrived to this conclusion with the program written here.

It basically takes every combination of $2$ primes $p,q$ such that $50<p,q<100$ $(53, 59, 61, 67, 71, 73, 79, 83, 89, 97)$ so that those primes in particular appear only one time in the factorization of $100!$ (becuase if it appears $n\ge2$ times, since $(x,x+1)=1$ either $x$ or $x+1$ would have to be divisible by $p^{n}$, making it harder to test), and searches for a solution of $k$ such that $$\frac{100!}{pq}\times k<4*99!\iff 25k<pq$$ in $$\frac{100!}{pq}\times k+1\equiv 0 \pmod{pq}$$ Aiming for the $x+1$ to complete the divisibility criterion.

Finally, it outputs your lucky numbers :)

chubakueno
  • 5,623
  • BTW, one of the problems by S. Konyagin (namely that one) was asked a few times in strong companies, but not answered. – user64494 Feb 28 '14 at 18:11
  • @user64494 I saw that question a while ago (from your post), and I couldn't solve it. I gave up after half an hour and expected to find a solution posted, but now I see that there is nothing until now... As a sidenote, I don't like to be biased by the source of a problem or by my current education level or my IQ(I don't know about it and I don't want to know), so I give a try at problems indiscriminately. It would surprise you the things you can do if you just see them without prejudices. (But obviously, everyone needs to have at least prejudice against Goldbach's conjecture :) ) – chubakueno Feb 28 '14 at 18:35
  • Also note that it's easy to see there are probably many solutions, because if you factorize $100!$ into primes, there's 25 distinct factors and by the Chinese Remainder Theorem you know there exists a solution for $x \equiv 0$ or $-1\ (mod p_i^{\alpha_i})$ regardless of how you set $0$'s or $-1$'s in the equations, so there's so $2^{25}$ solutions it would be really weird if one of them was not lower than $4\cdot 99! = \frac{100!}{25}$. – user2345215 Feb 28 '14 at 18:57
  • @user2345215 Yes, that is likely. I just chose to take the lowest hanging fruit, and luckily it was enough for this problem. In particular, this solution is even $<299!$. But it would be quite hard to catch 'em all* ... – chubakueno Feb 28 '14 at 19:06