0
$\begingroup$

This question is inspired from the video "FamousMathProbs1: Factoring large numbers into primes" by Wildberger and from this article about Galois theory.

So Galois theory is about radicals and polynomials. For example, does there exist a radical (a formula made from basic operations +, -, $\times$... that evaluates the root of a polynomial with rational coefficients) for a given polynomial.

It turns out that for polynomials of degree 5 and more, it doesn't exist! We can check that by computer.

Thanks to the fundamental theorem of galois theory, we have a deep idea of why radicals don't exist for polynomials of degree 5 and more. And basically, a polynomial must satisfy some "solvability" arguments to have a radical.

In the same sense, I was wondering, does there exist for every number something which will tell us if that number when factored into primes will give us for example a product of 2, 3 and 17 and not 2, 3 and 19 for example? Do such arguments exist?

Thank you and Happy PiDay!

$\endgroup$
5
  • $\begingroup$ I'm not sure what you mean, but for example if a number ends with a 5 or a 0, then 5 must be a prime factor in that number. If it does not, then 5 is not a prime factor in that number. Something like that? $\endgroup$
    – naslundx
    Mar 16, 2014 at 16:53
  • $\begingroup$ @naslundx What I really mean: Take as an example a polynomial of degree 2, how do we know it has real solutions? We simply compute its determinant $\Delta=b^2-4ac$. if we get $\Delta<0$ it doesn't have real solutions. That's the kind of arguments I'm searching for but instead of polynomials, we just have numbers! $\endgroup$
    – user135823
    Mar 16, 2014 at 16:57
  • 2
    $\begingroup$ @naslundx yes something like that apparently. but I doubt that exists for every prime. Euler said about primes,"primes something something mystery something something impenetrable for human minds" or something like that $\endgroup$
    – Guy
    Mar 16, 2014 at 16:59
  • $\begingroup$ @user135823 So you have a number, say 176. What would you like to find out? Not its prime factorization? $\endgroup$
    – naslundx
    Mar 16, 2014 at 17:00
  • $\begingroup$ @naslundx I want to know something that could determine for me the prime factors of 176. $\endgroup$
    – user135823
    Mar 16, 2014 at 17:06

1 Answer 1

Reset to default
0
$\begingroup$

There is no closed formula for calculating the prime factors of a given number $n$. There are algorithms for finding that out though, for example trying to divide $n$ with all primes $\leq \sqrt{n}$ and if the remainder is an integer, we know that that prime is a factor in $n$. Or if we know some/all divisors, we can start by prime factorizing them.

Of course, for large $n$, this quickly becomes a really heavy computation, even for our fastest computers. This is partly why different encryption systems (such as RSA) are safe - it's simply too computationally difficult to prime factorize a huge number (for now).

Quantum computers, if they become a practical reality, would do this much faster though, for example using Shor's algorithm.

$\endgroup$

You must log in to answer this question.

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