2
$\begingroup$

If I partition an integer and get the prime factorization of each partition, is there a way to tell if my original integer was a prime? For example, given the factorization of my partitions $$71 = (56) + (15) = (2^{3}\cdot 7^{1}) + (3^{1}\cdot 5^{1})$$

How can I find out if 71 is a prime number from these factorizations?

$\endgroup$
6
  • $\begingroup$ Do you mean $2^3\cdot 7^1$ and $3^1\cdot 5^1$ ? In this case, we know that the number cannot be divisibel by a prime less than $11$ which is here enough to prove that $71$ is prime. $\endgroup$
    – Peter
    Commented Dec 5, 2021 at 17:32
  • 1
    $\begingroup$ This however will only work for small numbers. $\endgroup$
    – Peter
    Commented Dec 5, 2021 at 17:35
  • $\begingroup$ Unfortunately, the method only works if we have TWO summands. $\endgroup$
    – Peter
    Commented Dec 5, 2021 at 17:42
  • $\begingroup$ Thank you. Is there a method that works for bigger numbers with more summands? $\endgroup$
    – murage kibicho
    Commented Dec 5, 2021 at 17:45
  • 1
    $\begingroup$ In special cases, it can work as well as in $2\cdot 3+3\cdot 5+2\cdot 5$ which actually shows that the given number is not divisible by $2,3$ or $5$. But again, we only have a very small number. This method is only good to rule out specific prime factors (if we are lucky , several at the same time). Primality tests for larger numbers work completely different. $\endgroup$
    – Peter
    Commented Dec 5, 2021 at 17:49

1 Answer 1

Reset to default
3
$\begingroup$

This is more work than it's worth, but if you partition a number into every possible combination of two addends, and if the members of every such partition are relatively prime (i.e. no prime factor of one member of a partition occurs in the other member of that partition), then the starting number is prime.

If the starting number is not prime, say $a\cdot b$, then there will be some partition $ac,ad$ where $c+d=b$ such that the members of the partition are not coprime.

$\endgroup$
1
  • $\begingroup$ You are right about the inefficiency. Even trial division beats this method drastically. But in fact, it would be a primality test. $\endgroup$
    – Peter
    Commented Dec 5, 2021 at 18:26

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .