1
$\begingroup$

Can a number $n=p_1\times p_2\times \dots\times p_k+1$ where $p_1, p_2,..., p_k$ are primes, be easily factorized? (the $k$ primes are known)

$\endgroup$
  • $\begingroup$ If there would be an easy way, then for example Collatz conjecture would be "easy" ... but at least you know $p_i \nmid n$. Btw I think you are using $n$ in two different meanings (number of primes and resulting number) $\endgroup$ – Sil Sep 22 at 11:57
3
$\begingroup$

If such a number could be easily factorised, then factorising $n$ would be as easy as factorising $n-1$. Which would be as easy as factorising $n-2$. And so on. So all you would have to do would be find a number $n-k$ that you can factorise, for some reasonably small $k$, and you could leapfrog your way to a factorisation of $n$.

While not conclusive, this argument suggests, to me at least, that such a number can't be easily factorised.

$\endgroup$
  • $\begingroup$ How do you obtain the factorization of $n+1$ from the factorization of $n$? $\endgroup$ – mip Sep 22 at 14:30
  • $\begingroup$ typically you wouldn't be able to in any simple way. $\endgroup$ – Roddy MacPhee Sep 22 at 14:35
  • $\begingroup$ @mip: That is equivalent to what your question is positing: given the factorisation $p_1\times p_2\times \dots\times p_k$ of an integer $m$, can we factorise $n = m+1$? $\endgroup$ – TonyK Sep 22 at 14:48
  • $\begingroup$ I see, thank you $\endgroup$ – mip Sep 22 at 18:40
1
$\begingroup$

Not exactly. Until we know one of the primes is 2 or not, we can't tell if this value is even or odd. Until we know if 3 is one of the primes, or an odd number of the primes are 2 mod 3, we can't tell if 3 is a factor. Unless an odd number of primes are 3 mod 4, your value won't be divisible by 4. etc. But that's in effect trial division. Also it can be prime. $2\cdot 3+1=7$ as an example.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.