3

How would I go about showing a number is prime, especially a very large number. Say I wanted to show that 43112621 is a prime number. How would I go about doing this without showing no other prime number prior to it?

Dexter Peters
  • 131

2 Answers2

3

It suffices to verify that the given number can't be divided by all numbers less or equal its square root. Why?

  • But the square root of 43112621 is roughly 6566.02. would I have to show, on paper, that every number less than or equal to 6566.02 does not divide 43112621. That seems far to time consuming. – Dexter Peters Nov 02 '13 at 19:31
  • 1
    @DexterPeters There are only 848 primes below 6566 (and these are probably found fastest by the sieve of Erathostenes). Then you need only trial divide by those primes. If you magicaly exhibit an integer solution of $x^2+y^2=p$ and show $\gcd(x,y)=1$, you may skip all primes $\equiv 3\pmod 4$ (so about half of them) from that list. Indeed, $3715^2+5414^2=43112621$ and $\gcd(3715,5414)=1$. – Hagen von Eitzen Nov 02 '13 at 19:53
  • 3
    @DexterPeters, if you have to do this by hand, you should probably state this in your question –  Nov 02 '13 at 20:14
0

There are multiple ways, one of them is to see if that number $p$ satisfies: $\tau(p)=2$ where $\tau$ is the tau function known as the divisor function.

When evaluating $\tau(43112621)$ we find a value of $2$. Therefore, $43112621$ is a prime number.

  • How did you evaluate the function $\tau$? – Lubin Nov 02 '13 at 21:01
  • @Lubin WolframAlpha.com –  Nov 02 '13 at 21:03
  • To me this is computationally very inefficient, even worse than checking for prime factors one by one, unless you have some methods for evaluating $\tau(n)$ effectively. Saying $\tau(p) = 2$ as a condition for prime seems to me a tautology that does not give effective computation right away. –  Nov 02 '13 at 23:37
  • @Sanchez There are lot of good approximations of the tau function. –  Nov 03 '13 at 13:15