2014 dxdy logo

Научный форум dxdy

Математика, Физика, Computer Science, Machine Learning, LaTeX, Механика и Техника, Химия,
Биология и Медицина, Экономика и Финансовая Математика, Гуманитарные науки




Начать новую тему Ответить на тему
 
 Делимость
Сообщение01.01.2012, 12:59 


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

 Профиль  
                  
 
 Re: Делимость
Сообщение01.01.2012, 16:49 
Заслуженный участник


09/02/06
4382
Москва
Пропустили условие, что х натуральное (иначе можно взять -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}$ одно из решений. Подобрать вручную меньшее решение сложно.

 Профиль  
                  
 
 Re: Делимость
Сообщение01.01.2012, 16:58 
Аватара пользователя


12/01/11
1320
Москва
Руст в сообщении #521954 писал(а):
Общее решение $x=d_1(-\frac{1}{d_1}\mod d_2)$.
Руст что означает эта запись?
И почему общее решение такое?

 Профиль  
                  
 
 Re: Делимость
Сообщение01.01.2012, 17:28 
Заслуженный участник


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

 Профиль  
                  
 
 Re: Делимость
Сообщение01.01.2012, 17:33 
Заслуженный участник


02/08/10
629
Руст в сообщении #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!$

 Профиль  
                  
 
 Re: Делимость
Сообщение01.01.2012, 18:33 
Заслуженный участник


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

 Профиль  
                  
 
 Re: Делимость
Сообщение01.01.2012, 20:38 
Заслуженный участник


02/08/10
629
Руст в сообщении #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}$

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

 Профиль  
                  
 
 Re: Делимость
Сообщение02.01.2012, 10:35 
Заслуженный участник


09/02/06
4382
Москва
MrDindows в сообщении #522005 писал(а):
Кстати, там для 53 вроде как не на 3 надо домножать, а на 14...

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

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

 Профиль  
                  
 
 Re: Делимость
Сообщение02.01.2012, 12:47 
Заслуженный участник


02/08/10
629

(Код)

Код:
#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$

 Профиль  
                  
Показать сообщения за:  Поле сортировки  
Начать новую тему Ответить на тему  [ Сообщений: 9 ] 

Модераторы: Модераторы Математики, Супермодераторы



Кто сейчас на конференции

Сейчас этот форум просматривают: нет зарегистрированных пользователей


Вы не можете начинать темы
Вы не можете отвечать на сообщения
Вы не можете редактировать свои сообщения
Вы не можете удалять свои сообщения
Вы не можете добавлять вложения

Найти:
Powered by phpBB © 2000, 2002, 2005, 2007 phpBB Group