Делимость

[RFZ]

Здравствуйте!
Помогите пожалуйста решить такую олимпиадную задачу:
Докажите, что существует такое $x<4\cdot 99!$ , что $x(x+1)$ делится на $100!$.

[Руст]

Пропустили условие, что х натуральное (иначе можно взять -100!).
Общее решение $x=d_1(-\frac{1}{d_1}\mod d_2)$, где $d_1d_2=100!,(d_1,d_2)=1$. Остается подобрать соответствующее $d_1,d_2=\frac{100!}{d_1}$.
Если не ошибся при $d_2=53$ получаем $-\frac{1}{d_1}=3$, т.е. $x=\frac{3*100!}{53}$ одно из решений. Подобрать вручную меньшее решение сложно.

[Whitaker]

Руст в сообщении #521954 писал(а):

Общее решение $x=d_1(-\frac{1}{d_1}\mod d_2)$.

Руст что означает эта запись?
И почему общее решение такое?

[Руст]

Это означает $x=ad_1=\frac{a*100!}{d}$, где после сокращения на d
$a=\frac{d}{100!}=-1\mod d=d_2$.

[MrDindows]

Руст в сообщении #521954 писал(а):

Пропустили условие, что х натуральное (иначе можно взять -100!).
Общее решение $x=d_1(-\frac{1}{d_1}\mod d_2)$, где $d_1d_2=100!,(d_1,d_2)=1$. Остается подобрать соответствующее $d_1,d_2=\frac{100!}{d_1}$.
Если не ошибся при $d_2=53$ получаем $-\frac{1}{d_1}=3$, т.е. $x=\frac{3*100!}{53}$ одно из решений. Подобрать вручную меньшее решение сложно.

Но $\frac{3 \cdot 100!}{53}>4 \cdot 99!$

[Руст]

Да. Но сложно перебрать даже решения с одним простым $d=d_2=p^k, k=v_p(100!)$. Можно комбинировать с двумя простыми. Вообще, учитывая, что число решений $1\le x\le 100!$ ровно $2^{25},\pi(100)=25$, можно надеяться, что найдутся и малые решения.

[MrDindows]

Руст в сообщении #521982 писал(а):

Да. Но сложно перебрать даже решения с одним простым $d=d_2=p^k, k=v_p(100!)$. Можно комбинировать с двумя простыми. Вообще, учитывая, что число решений $1\le x\le 100!$ ровно $2^{25},\pi(100)=25$, можно надеяться, что найдутся и малые решения.

Перебрал все варианты с одним простым, и ни один не подошёл)
Кстати, там для 53 вроде как не на 3 надо домножать, а на 14...

Для двух простых вроде бы есть решение=)
$x=\frac{501\cdot 100!}{41^2\cdot 71}$

*Редактирую уже третий раз, ибо были баги в проге)

[Руст]

MrDindows в сообщении #522005 писал(а):

Кстати, там для 53 вроде как не на 3 надо домножать, а на 14...

*Редактирую уже третий раз, ибо были баги в проге)

Надо умножаеь на $\frac{-53}{100!}\mod 53=\frac{1}{5!}\mod 53=\frac{1}{14}\mod 53=19$. Ошибка и у вас и у меня.
Правильно ли программировали?

[MrDindows]

(Код)

#include <iostream.h>
#include <conio.h>
#include <math.h>
typedef long long ll;

void extended_euclid(ll a, ll b, ll *x, ll *y, ll *d)
{ ll q, r, x1, x2, y1, y2;
  if (b == 0) {
    *d = a, *x = 1, *y = 0;
    return;  }
  x2 = 1, x1 = 0, y2 = 0, y1 = 1;
  while (b > 0) {
    q = a / b, r = a - q * b;
    *x = x2 - q * x1, *y = y2 - q * y1;
    a = b, b = r;
    x2 = x1, x1 = *x, y2 = y1, y1 = *y;  }
  *d = a, *x = x2, *y = y2;}
  
ll inverse(ll a, ll n)
{  ll d, x, y;
  extended_euclid(a, n, &x, &y, &d);
  if (d == 1) if (x>0) return x; else return (x+n);
  return 0;}

int main(){
    ll i,j,k,n,t,l;                // j - простое число, 
    for (j=5;j<=97;j++)  {         // n - 100!(без множителей j) по модулю j,
        bool e=true;               // t - то, на что надо домножать
    for (i=2;i<=sqrt(j);i++) if (j%i==0) {e=false;break;}
    if (e) {
    n=1;
   ll p =(ll)(pow(j,100/j+100/(j*j)+100/(j*j*j)+100/(j*j*j*j)));   
  for (i=2;i<=100;i++) {
      k=i;
      while (k%j==0) k/=j;

      n=(n*k)%(p);}
   t=p-inverse(n,p);
   l=100*t/p;
   cout<<j<<" "<<t<<endl;
   
   if (100*t/p<4) cout<<"YES "<<j<<" "<<t<<endl;}}
    getch();
    return 0;
    }

Да вроде. А откуда вы взяли первое сравнение?
Я ещё и проверил:
$\frac{100!}{53} \ \mod \ 53 = 34$ http://www.wolframalpha.com/input/?i=100%21%2F53+mod+53

$34 \cdot 14 =476= 53\cdot 9 -1$