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

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.

#### Step 1. Use division by trial

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

).

#### 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.

#### 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.
• ). 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

#### 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

#### 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

#### 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).

#### 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.

#### 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

#### 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

#### 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

#### 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

#### 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

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

• Answer = (1 * 97 * 27 + 2 * 35 * 61)% (97 * 35)
• Answer = (2619 + 4270)% 3395

#### 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.

#### 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.

#### 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.