Integer Factor Congruence

Question

Given an integer $N$, with unknown prime factors $f_1$, $f_2$ ... $f_n$, and given unique integers $k_1$, $k_2$ ... $k_n$, with $\sqrt{N} \geq k_i>2$ for all $i$ such that $$f_1 \equiv 1\pmod {k_1}$$ $$f_2 \equiv 1\pmod {k_2}$$ $$f_n \equiv 1\pmod {k_n}$$ Does knowing $k_1$, $k_2$ ... $k_n$ in any way help to find $f_1$, $f_2$ ... $f_n$?

Answer 1

lulu made the point that, any time $k_i$ are all constant, you don't get much in way of help. Here are a few things that will:

• Noting that $k_i$ multiplied by the negative of it's multiplicative inverse mod any prime that isn't $f_i$, is out as a higher equivalent modulus, because it would add to 0 mod the tried prime.

This means the following:

• odd $k_i$ can't have odd multipliers.
• $k_i\equiv 1\pmod 3$ can't have a multiplier $r\equiv 2\pmod 3$
• $k_i\equiv 2\pmod 3$ can't have a multiplier $r\equiv 1\pmod 3$
• $k_i\equiv 1\pmod 5$ can't have a multiplier $r\equiv 4\pmod 5$

This and possibly confining their range, may help a lot.