Перейти до вмісту

Операції у модульній арифметиці


Повідомлень в темі: 6

#1 Гетьман

    I am forsaken (c) Sylvanas

  • Користувачі
  • PipPipPipPipPipPipPipPipPipPip
  • 2480 повідомлень
  • Стать:Чоловік
  • Місто:Leopolis novus

Відправлено 09.01.2011 – 22:07

  • 6
Сьогодні їдучи у маршрутці подзвонив друг. І задав задачку. Нехай маємо просте число p, для якого число (p+1)/2 - просте. Нехай ми маємо центральний біноміальний коефіцієнт z=C^(p-1/2)_p. Задача - знайти o=z mod p^3 (або остачу від ділення z на p в кубі).
Куди я просунувся:
1. Очевидно, що біноміальний коефіцієнт ділиться на p. Тому, остача має ділитися на p.
2. Я вирішив розв'язати цю задачу їдучи у маршрутці для остачі при діленні на p^2. Підрахунки для p=7 та p=13 дали результатами, що остача рівна 2*p. На пальцях у маршрутці я довів цей факт. Прийшовши додому, я накатав наступну прогу:
program ddd;
function invers(a,p:longint):longint;
var i:longint;
begin
invers:=0;
for i:=1 to p-1 do
if i*a mod p = 1 then invers:=i;
end;
function isprime(p:longint):boolean;
var i:longint;
begin
isprime:=true;
for i:=2 to trunc(sqrt(p))+1 do
if p mod i = 0 then isprime:=false;
end;
var i,j,k:longint; a:array[1..255] of longint; f,g:text;
begin
assign(f,'e:/test/primes.txt');
assign(g,'e:/test/quadrat.txt');
{rewrite(f);
writeln(f,3);
for i:=1 to 16000 do begin
j:=2*i+1;
if isprime(j) and isprime(i+1) then writeln(f,j);
end;  }
reset(f);
rewrite(g);
while not eof(f) do begin
readln(f,i);
k:=1;
for j:=1 to i-1 do
k:=k*j mod i;
for j:=1 to i-1 div 2 do
k:=(k*invers(j,i) mod i)*invers(j,i) mod i;
writeln(g,i,' ',k);
end;
close(f); close(g);
readln
end.
Коли ми відкриваємо фігурні дужки і беремо close(g); у фігурні дужки, то формуємо файлеґ із простих чисел, які задовольняють дану властивість.
Коли ми повертаємося до коду, що написаний у програмі, то ми формуємо другий файлеґ, який дає нам цю остачу, поділену на p. Щось я поламав у файлі коли пробував модифікувати, зараз виправляти не вийде бо несамовито хочу спати після важкого трудодня, але файл заповнюється числами і відповідними їм 2 (завжди, що підтверджує доведену на пальцях лему).
Мораль: треба довести цей цікавий факт. Заодно і ще кілька фактів, чим займуся завтра.
3. Залишається задача обчислити остачу при діленні на p^3. По суті, модифікувавши прогу це можна зробити, але хотілося б формулу отримати. Завтра також займуся цим.

З. І. Швидше за все тут не з'явиться жодного допису по темі, але я її створюю щоб просто не забути, бо зараз умираю, так спати хочу.
З. З. І. Я просив поставити на форум TeX, усім влом, бачте. Що ж, дякую, панове.

#2 FT232BM

    私は人々嫌い

  • Користувачі
  • PipPipPipPipPipPipPipPipPipPip
  • 3435 повідомлень
  • Стать:Чоловік
  • Місто:Київ->НТУУ "КПІ"

Відправлено 09.01.2011 – 22:14

Перегляд дописуГетьман (9.01.2011 22:07) писав:

З. І. Швидше за все тут не з'явиться жодного допису по темі, але я її створюю щоб просто не забути, бо зараз умираю, так спати хочу.
З. З. І. Я просив поставити на форум TeX, усім влом, бачте. Що ж, дякую, панове.
Ех да, важко осягнути таке. На рахунок TeX: да, да, і ще раз ДА.
Останній раз коли я вимагав TeX, мене послали читати якийсь ман по юнікоду. Хотів вшарити але не вшарив, як там системи диф. рівнянь складати і при чому тут юнікод взагалі.
Походу ТеХа під цей движок нема. А от на dxdy.ru єєєє, я заздрю

Повідомлення відредагував FT232BM: 09.01.2011 – 22:15

  • 0

#3 Гетьман

    I am forsaken (c) Sylvanas

  • Користувачі
  • PipPipPipPipPipPipPipPipPipPip
  • 2480 повідомлень
  • Стать:Чоловік
  • Місто:Leopolis novus

Відправлено 26.03.2011 – 21:45

http://latex.codecog...\cos\frac{1}{n} - збіжна. Вона збіжна тому, що фундаментальна. А фундаментальна вона тому, що http://latex.codecog...+k}-\frac{1}{n})\sin(\frac{1}{n}+\frac{1}{n+k}). Перший множник прямує до нуля, бо http://latex.codecogs.com/gif.latex?y'(0)=0-1=-1;
http://latex.codecog...gif.latex?y^{(4)}=...
і так до посиніння. Два знайшов, решту сам шукай.
Вкінці запис: http://latex.codecog......=-x+8x^3+... (розклад в околі нуля, працюєш доки набереш 4 ненульових члени)
  • 0

#4 Twinkle

    Старійшина

  • Користувачі
  • PipPipPipPipPipPipPipPipPipPip
  • 1625 повідомлень
  • Стать:Жінка
  • Місто:Львів

Відправлено 26.03.2011 – 23:31

Перегляд дописуГетьман (9.01.2011 23:07) писав:

Сьогодні їдучи у маршрутці подзвонив друг.

А навіщо такі деталі про перебування друга під час дзвінка?

І ще: це ж Паскаль, правда? :gryzin:
  • 0

#5 Гетьман

    I am forsaken (c) Sylvanas

  • Користувачі
  • PipPipPipPipPipPipPipPipPipPip
  • 2480 повідомлень
  • Стать:Чоловік
  • Місто:Leopolis novus

Відправлено 27.03.2011 – 08:45

Халепа, помилився отута, має бути:

Перегляд дописуГетьман (26.03.2011 21:45) писав:

Вкінці запис: http://latex.codecog...ac{8}{6}x^3+... (розклад в околі нуля, працюєш доки набереш 4 ненульових члени)

Перегляд дописуTwinkle (26.03.2011 23:31) писав:

А навіщо такі деталі про перебування друга під час дзвінка?

І ще: це ж Паскаль, правда? :gryzin:
Нє, я їхав у маршрутці. То такє. Мова - Паскаль, до ВінАПІшних у мене якась дивна нелюбов, хоч мене ним в універі пробували навчити.
  • 0

#6 Twinkle

    Старійшина

  • Користувачі
  • PipPipPipPipPipPipPipPipPipPip
  • 1625 повідомлень
  • Стать:Жінка
  • Місто:Львів

Відправлено 27.03.2011 – 12:03

Перегляд дописуГетьман (27.03.2011 09:45) писав:

Нє, я їхав у маршрутці.

То був тонкий натяк на граматично неправильну конструкцію :gryzin:

Перегляд дописуГетьман (27.03.2011 09:45) писав:

Мова - Паскаль

Це не може не тішити, бо, читаючи код, принаймні щось розумію :ggggg:
  • 0

#7 Гетьман

    I am forsaken (c) Sylvanas

  • Користувачі
  • PipPipPipPipPipPipPipPipPipPip
  • 2480 повідомлень
  • Стать:Чоловік
  • Місто:Leopolis novus

Відправлено 30.05.2011 – 15:19

Перша зодача. Оскілько http://latex.codecog...if.latex?p=0,01 - мале, то ми можемо обчислити ймовірність наближено за допомогою розподілу Пуасона. http://latex.codecog...x?\lambda=pn=1.
1) http://latex.codecog...-p_1-p_2=0,019.
Друга зодача. Вважатимемо ймовірність загубити кожну кульку рівнозначною. Тоді імовірність, що загубили білу кульку - http://latex.codecog...ex?\frac{7}{11}, а чорну - http://latex.codecog...x?\frac{4}{11}. У першому випадку імовірність витягнути білу кульку рівна http://latex.codecog...-1}=\frac{3}{5}, у другому випадку - http://latex.codecog...}=\frac{7}{10}. Події загублювання та витягання кульки - незалежні, загублення білої та чорної кульки - несумісні. Тому:
http://latex.codecog...}=\frac{7}{11}. Кумедно, але імовірність не змінилася. Може, це можна якось довести, але мені влом думати.
Третя зодача. З того, що http://latex.codecog...m/gif.latex?M(X)=1,4 маємо, що http://latex.codecog...4=p_1x_1+(1-p_1)x_2. http://latex.codecog...gif.latex?M(X^2)=p_1x_1^2+(1-p_1)x_2^2. http://latex.codecog...m/gif.latex?D(X)=M(X^2)-M^2(X). Отримуємо систему рівнянь:
http://latex.codecog...m/gif.latex?x_1 та http://latex.codecog.../gif.latex?x_2. Та й усьо на тому. Квадратні рівняння, сподіваюсь, розв'язувати як не забув.
  • 0



Кількість користувачів, що читають цю тему: 1

0 користувачів, 1 гостей, 0 анонімних


Магазин кубиков Рубика Cubes.in.ua