a/b mod m = (a mod m)/(b mod m)?Имеет ли a/b mod m = (mod m)/(b mod m)?
Я пытаюсь найти nCr mod m для очень больших чисел. Если a/b mod m = (a mod m)/(b mod m), тогда подумайте, что я разрешу свою проблему.
Это для Project Euler. Я использую формулу nCr, используя факториалы.
No.
Если у вас есть a=8, b=2, m=2 то есть a/b mod m = 8/2 mod 2 = 4 mod 2 = 0
и (a mod m)/(b mod m) = (8 mod 2)/(2 mod 2) = 0/0 = NaN
NaN не равна 0.
Эта идентификация не поддерживается. Вот контрпример:
Let a = 21, b = 7, m = 7.
Then (21/7) = 3 and 3 mod 7 = 3
Alternately, 21 mod 7 = 0 and 7 mod 7 = 0.
But 0/0 is undefined (and certainly not 3).
Таким образом, ваша идентификация не поддерживается. Тем не менее, я почти уверен, что он будет иметь место, если m и b взаимно просты.
Действительно. Если 'b' и' m' взаимно просты, существует 'c' такое, что' b * c mod m = 1'. Тогда '(a/b) mod m == (a/b) * (c * b) mod m == (a * c) mod m == (mod m) * c mod m' и аналогично для' b mod m'. –
Вы можете использовать следующую ссылку, чтобы оценить (а/б) тойт ..... http://mathworld.wolfram.com/Congruence.html
Ответ для оценки дается в конце ..
Это полезно, но это должен быть комментарий, поскольку он не отвечает непосредственно на его вопрос. –
Если б = т, то у вас будет деление на ноль. – poke
Я так не думаю. Все, что вам нужно, это один пример, чтобы доказать это неправильно, поэтому попробуйте несколько разных наборов чисел, например 19, 9 и 4. –
Являются ли 'a' и' b' относительно первыми с 'm'? –