How to tell if a number is prime (with pictures)

Table of contents:

How to tell if a number is prime (with pictures)
How to tell if a number is prime (with pictures)
Anonim

Prime numbers are divisible only by themselves and 1. On the other hand, all the others are called composite numbers. There are many methods of knowing if a number is prime, but there is always a certain margin of error. There are also precise but extremely slow tests for analyzing large numbers, as well as others that are much faster, but which can give false results. In this article, you will see some options for detecting a prime number based on its size.

Steps

Part 1 of 3: Using Different Tests to Detect a Prime Number

Note:

in all formulas, n is the number whose primality you want to test.

Check if a Number Is Prime Step 1
Check if a Number Is Prime Step 1

Step 1. Use division by trial

Divide n by each prime number from 2 up to the ceiling function (n { displaystyle { sqrt {n}}}

).

Check if a Number Is Prime Step 2
Check if a Number Is Prime Step 2

Step 2. Do Fermat's Little Theorem

Warning: you could get false positives, even for all values of a.

  • Assign an integer value to a such that 2 ≤ a ≤ n - 1.
  • Yes to (mod n) = a (mod n), so “n” is probably a prime number. If this is not true, then "n" is not prime.
  • Do the same with different values of a to make sure it is really prime.
Check if a Number Is Prime Step 3
Check if a Number Is Prime Step 3

Step 3. Perform the Miller-Rabin primality test

Warning: you could get false positives, but it rarely happens at multiple values of a.

  • Find the values of “s” and “d” such that n − 1 = 2s ∗ d { displaystyle n-1 = 2 ^ {s} * d}

  • Asígnale un valor entero a a de modo tal que 2 ≤ a ≤ n - 1.
  • Si ad = +1 (mod n) o -1 (mod n), entonces “n” probablemente sea un número primo. Ahora pasa al resultado de la prueba; de lo contrario, ve al siguiente paso.
  • Eleva la respuesta al cuadrado (a2d{displaystyle a^{2d}}

    • ). Si este es igual a +1 (mod n) o -1 (mod n), ve al resultado de la prueba. De lo contrario, repite (a4d{displaystyle a^{4d}}

    etc.) hasta que a2s−1d{displaystyle a^{2^{s-1}d}}

  • Resultado de la prueba: si “n” pasa la prueba, asígnale diferentes valores de a para garantizar su primalidad.

Parte 2 de 3: Comprender las pruebas para detectar números primos

Check if a Number Is Prime Step 4
Check if a Number Is Prime Step 4

Step 1. Understand the trial division method

According to the definition of primality, n is only prime if it cannot be divided equally between integers such as 2 or greater. The dad formula saves you time by discarding unnecessary tests (eg: after testing 3, you don't need to do the same with 9).

The ceiling (x) function rounds x to the nearest whole number ≥ x

Check if a Number Is Prime Step 5
Check if a Number Is Prime Step 5

Step 2. Understand modular arithmetic

The operation "x mod y" (short for “modulus”) means “divide“x”by“y”and find the remainder.” In other words, in modular arithmetic, numbers return to zero after reaching a certain known value as the “modulo.” A clock counts at modulo 12 (that is, it goes from 10 to 11 to 12) and then back to 1.

Many calculators include a "mod" button, but see the last part of this section to learn how to solve it by hand for large numbers

Check if a Number Is Prime Step 6
Check if a Number Is Prime Step 6

Step 3. Consider the problems with Fermat's Little Theorem

All numbers that do not pass this test are composite (not prime), but unfortunately, those that do pass only are probably prime. If you want to safely avoid false positives, look for n in a list of "Carmichael numbers" (which pass this test all the time) and "Fermat pseudo cousins" (which pass this test only for some values of a).

Check if a Number Is Prime Step 7
Check if a Number Is Prime Step 7

Step 4. Use the Miller-Rabin primality test whenever appropriate

While complex to perform by hand, this test is generally done using software. It does not take long and has few false positives compared to the Fermat method. A composite number never gives a false positive for more than ¼ of the values of a. If you choose several values of a at random and pass this test, you can be almost certain that n is a prime.

Check if a Number Is Prime Step 8
Check if a Number Is Prime Step 8

Step 5. Do modular arithmetic to analyze large numbers

If you don't have a calculator with the "mod" function, or if the one you have can't represent such large numbers, use the properties of exponents and modular arithmetic to make the process easier. In this case, we will use 350 { displaystyle 3 ^ {50}} as an example

mod 50:

  • Reescribe la expresión con exponentes más manejables: (325∗325){displaystyle (3^{25}*3^{25})}

    • mod 50 (quizás necesites descomonerlo aún más si vas a realizar el cálculo a mano).

  • (325∗325){displaystyle (3^{25}*3^{25})}

    • mod 50 = (325{displaystyle (3^{25}}

    mod 50 ∗325{displaystyle *3^{25}}

    mod 50) mod 50 (esta es una propiedad de la multiplicación modular).

  • 325{displaystyle 3^{25}}

    • mod 50 = 43.

  • (325{displaystyle (3^{25}}

    • mod 50 ∗325{displaystyle *3^{25}}

    mod 50) mod 50 = (43∗43){displaystyle (43*43)}

    mod 50

  • =1849{displaystyle =1849}

    • mod 50

  • =49{displaystyle =49}

Parte 3 de 3: Utilizar el teorema chino del resto

Check if a Number Is Prime Step 9
Check if a Number Is Prime Step 9

Step 1. Choose two numbers

One of them should not be a prime, while the other should be the one you need to analyze to detect its primality.

  • "Prime1" = 35
  • prime2 = 97
Check if a Number Is Prime Step 10
Check if a Number Is Prime Step 10

Step 2. Choose two data points that are greater than zero and less than prime1 and prime2 respectively

They cannot be the same.

  • data1 = 1
  • data2 = 2
Check if a Number Is Prime Step 11
Check if a Number Is Prime Step 11

Step 3. Find the multiplicative inverse (MI) of the prime1 and prime2 numbers

  • Calculate the MI:

    • IM1 = prime2 ^ -1 mod prime1
    • IM2 = prime1 ^ -1 mod prime2

  • Only in the case of prime numbers (you will get a number for composite numbers, but it will not be their MI):

    • IM1 = (prime2 ^ (prime1-2))% prime1
    • IM2 = (prime1 ^ (prime2-2))% prime2

  • For instance:

    • IM1 = (97 ^ 33)% 35
    • IM2 = (35 ^ 95)% 97
Check if a Number Is Prime Step 12
Check if a Number Is Prime Step 12

Step 4. Create a binary conversion table for each IM until you reach log2 of the module

  • For IM1:

    • F (1) = prime2% prime1 = 97% 35 = 27
    • F (2) = F (1) * F (1)% prime1 = 27 * 27% 35 = 29
    • F (4) = F (2) * F (2)% prime1 = 29 * 29% 35 = 1
    • F (8) = F (4) * F (4)% prime1 = 1 * 1% 35 = 1
    • F (16) = F (8) * F (8)% prime1 = 1 * 1% 35 = 1
    • F (32) = F (16) * F (16)% prime1 = 1 * 1% 35 = 1

  • Perform binary conversion of prime1 - 2

    • 35 -2 = 33 (10001) base 2
    • IMI1 = F (33) = F (32) * F (1) mod 35
    • IM1 = F (33) = 1 * 27 mod 35
    • IM1 = 27

  • For IM2:

    • F (1) = prime1% prime2 = 35% 97 = 35
    • F (2) = F (1) * F (1)% prime2 = 35 * 35 mod 97 = 61
    • F (4) = F (2) * F (2)% prime2 = 61 * 61 mod 97 = 35
    • F (8) = F (4) * F (4)% prime2 = 35 * 35 mod 97 = 61
    • F (16) = F (8) * F (8)% prime2 = 61 * 61 mod 97 = 35
    • F (32) = F (16) * F (16)% prime2 = 35 * 35 mod 97 = 61
    • F (64) = F (32) * F (32)% prime2 = 61 * 61 mod 97 = 35
    • F (128) = F (64) * F (64)% prime2 = 35 * 35 mod 97 = 61

  • Perform binary conversion of prime2 - 2

    • 97 - 2 = 95 = (1011111) base 2
    • IM2 = (((((F (64) * F (16)% 97) * F (8)% 97) * F (4)% 97) * F (2)% 97) * F (1)% 97)
    • IM2 = (((((35 * 35)% 97) * 61)% 97) * 35% 97) * 61% 97) * 35% 97)
    • IM2 = 61
Check if a Number Is Prime Step 13
Check if a Number Is Prime Step 13

Step 5. Calculate (data1 * prime2 * IM1 + data2 * prime1 * IM2)% (prime1 * prime2)

  • Answer = (1 * 97 * 27 + 2 * 35 * 61)% (97 * 35)
  • Answer = (2619 + 4270)% 3395
  • Answer = 99
Check if a Number Is Prime Step 14
Check if a Number Is Prime Step 14

Step 6. Verify that “prime1” is not a prime number

  • Calculate (answer - data1)% prime1.
  • 99 -1 % 35 = 28.
  • Since 28 is greater than 0, it means that 35 is not a prime number.
Check if a Number Is Prime Step 15
Check if a Number Is Prime Step 15

Step 7. Check if prime2 is a prime number

  • Calculate (answer - data2)% prime2
  • 99 - 2 % 97 = 0
  • Since 0 equals 0, it means that 97 is probably a prime number.
Check if a Number Is Prime Step 16
Check if a Number Is Prime Step 16

Step 8. Repeat steps 1 through 7 at least two more times

  • If in step 7 you get a 0:

    • Use a different "prime1", where prime1 is not a prime number.
    • Use a different prime1, where prime1 is not a real number. In this case, steps 6 and 7 must equal 0.
    • Use different data points for data1 and data2.
  • If step 7 always returns 0, there is a very high probability that prime2 is a prime number.
  • In some cases, steps 1 through 7 may fail if the first number is not prime and the second is a factor of the composite number “prime1”. It works in all cases where both numbers are prime.
  • The reason steps 1 through 7 are repeated is because there are some occasions when, even when prime1 and prime2 are composite, step 7 still returns 0, either for one or both numbers. However, these circumstances are rare. When converting prime1 to a different composite number, if prime2 is not prime, it will certainly equal zero in step 7. Except for the case where “prime1” is a factor of prime2, prime numbers will always equal zero in step 7.

Advice

  • The 168 prime numbers less than 1000 are as follows: 2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71, 73, 79, 83, 89, 97, 101, 103, 107, 109, 113, 127, 131, 137, 139, 149, 151, 157, 163, 167, 173, 179, 181, 191, 193, 197, 199, 211, 223, 227, 229, 233, 239, 241, 251, 257, 263, 269, 271, 277, 281, 283, 293, 307, 311, 313, 317, 331, 337, 347, 349, 353, 359, 367, 373, 379, 383, 389, 397, 401, 409, 419, 421, 431, 433, 439, 443, 449, 457, 461, 463, 467, 479, 487, 491, 499, 503, 509, 521, 523, 541, 547, 557, 563, 569, 571, 577, 587, 593, 599, 601, 607, 613, 617, 619, 631, 641, 643, 647, 653, 659, 661, 673, 677, 683, 691, 701, 709, 719, 727, 733, 739, 743, 751, 757, 761, 769, 773, 787, 797, 809, 811, 821, 823, 827, 829, 839, 853, 857, 859, 863, 877, 881, 883, 887, 907, 911, 919, 929, 937, 941, 947, 953, 967, 971, 977, 983, 991, 997
  • Although the tentative division method is slower than the other sophisticated methods specific to large numbers, it is still very efficient for small numbers. Even to find out whether large numbers are prime or not, it is not uncommon for small factors to be checked first before using a more advanced method in the event that no such factors are found.

Popular by topic