Простые множители суммы натуральных чисел
Есть два натуральных числа x и y и их сумма z, можно ли узнать все простые множители z, при этом зная простые множители чисел x и y? При этом не используя алгоритмы факторизации (т е разбития на простые множители). То есть дает ли выгоду в вычислении знание простых множителей слагаемых суммы?
Что-то сказать в этом случае можно. 1) Если x и y одновременно делятся на какое-то число m, то тогда и их сумма тоже делится на m. Это можно использовать и при разложении на простые множители. Пусть есть простое число p такое, что оно входит в разложение на простые и числа x, и числа y. Пусть в разложении x оно встречается t раз, а в разложении y -- s раз. Тогда в разложении z число p тоже встретиться, причем встретиться оно ровно min{s,t} раз. 2) Если простое число p таково, что оно входит в разложение на простые только одного из чисел x,y, но не входит в разложение другого, тогда в разложение z оно тоже не войдет.
нет, возьмите к примеру четыре и девять, имеем двойки и тройки, а в сумме триннадцать, вообще простое число.