Si no tengo una computadora en la mano (o una aplicación), ¿cómo puedo saber que $1637$ es primo?

Question

Si no tengo una computadora en la mano (o una aplicación), ¿cómo puedo saber que $1637$ es un número primo?

Yo factorizada el número de $99857$ $1637\times 61$ y el equipo me dijo que $1637$ es un primo. Así que sería fácil a todos a conocer este sin ella?

Answer 1

Si no fue el primer, habría un primer factor menor que o igual a su raíz cuadrada. Desde$$40^2=1\,600<1\,637$$and$$41^2-40^2=(41-40)\times(41+40)=81,$$it is clear that $40<\sqrt{1\,637}<41$. So, all you have to do is to check whether $1\,637$ is a multiple of one of the twelve numbers $2,3,5,\ldots,37$.

Answer 2

Para un determinado número de $n$ y el candidato divisor $d \in \mathbb{P}$, d | n (leer "d divide a n") iff d | (n + kd).

Este truco puede ser utilizado para acelerar el cálculo mental, que está tratando de hacer. Por ejemplo, supongamos $n = 1637$$d = 17$. El objetivo es reducir la instrucción d | n en una forma más intuitiva verdadera o falsa declaración.

Si 17 | 1637, a continuación, 17 | (1637 +(-1)*17)
17 | 1620
17 | 162*10
17 | 162
17 | (162 + 17)
17 | 179
17 | (170 + 9)
17 | 9,

Lo cual es falso, por lo que 17 no dividir 1637.

Enjuague y repita. (Divertido!)

Answer 3

Respuesta completa: esto es bastante tedioso. Muestra de lo útil que las calculadoras son!

Como otros han mencionado, $1637<41^2$ tan sólo comprobar si es divisible por $$2,3,5,7,11,13,17,19,23,29,31,37.$$ podemos descartar

• $2$ $1637$ es impar

• $3$ como la suma de los dígitos de $1637$ $17$ que no es divisible por $3$

• $5$ $1637$ no termina en $0$ o $5$

• $11$ como la alternancia suma es $1-6+3-7=-9$ que no es divisible por $11$.

Tiempo de congruencias. Por la fuerza bruta,

• $1637\equiv1400+210+28-1\equiv-1\pmod7$ por lo tanto, rechazar $7$.

• $1637\equiv1300+260+78-1\equiv-1\pmod{13}$ por lo tanto, rechazar $13$.

• $1637\equiv1700-68+5\equiv5\pmod{17}$ por lo tanto, rechazar $17$.

• $1637\equiv1900-380+117\equiv117\equiv3\pmod{19}$ por lo tanto, rechazar $19$.

• $1637\equiv1840-184-19\equiv-19\equiv4\pmod{23}$ por lo tanto, rechazar $23$.

• $1637\equiv1740-174-71\equiv-71\equiv13\pmod{29}$ por lo tanto, rechazar $29$.

• $1637\equiv1550+93-7\equiv-7\pmod{31}$ por lo tanto, rechazar $31$.

• $1637\equiv1850-185-28\equiv-28\pmod{37}$ por lo tanto, rechazar $37$.

HECHO!

El truco es empezar con el número más cercano a $1637$ que es divisible por los primos de que estás trabajando con el modulo.

Answer 4

Si usted tiene un número de menos de un millón o así, el de Miller-Rabin prueba de primalidad perfectamente a identificar primalidad con $a=2$ o $a=3$. Esto es bastante fácil de ejecutar con la mano. Edit: Acaba de ejecutar realmente esta a mano, y el cálculo de estas grandes potencias mod 409 es bastante laborioso. Creo que esto es todavía factible, no no es tan simple como recuerdo.

https://en.wikipedia.org/wiki/Miller%E2%80%93Rabin_primality_test

Answer 5

Si podemos demostrar que $1637$ tiene exactamente una representación como una suma de dos cuadrados, entonces sabemos que es primo.

Si hay una representación de la misma debe ser de la forma $1637=(2m-1)^2+(2n)^2$, lo que implica

$$m^2-m+n^2=409$$

Desde $m^2-m=m(m-1)$ es aún, debemos tener $n$ impar, en cuyo caso $8\mid(409-n^2)$, por lo que cualquiera de las $8\mid m$ o $8\mid m-1$, es decir, $m=8h$ o $m=8h+1$ algunos $h$. Escrito $n=2k-1$, nos encontramos con cualquiera de las $64h^2-8h+4k^2-4k+1=409$ o $64h^2+8h+4k^2-4k+1=409$, que se reduce a

$$16h^2\pm2h+k^2-k=102$$

con $m=8h$ si el signo negativo se utiliza y $m=8h-1$ es el signo más se utiliza.

Es claro que $16h^2\pm2h+k^2-k\gt102$ si $h\ge3$, tan sólo tenemos que comprobar los valores $h=0$, $1$ y $2$.

Para $h=0$, la ecuación de $k(k-1)=102=53\cdot2$ no tiene soluciones.

Para $h=1$, las ecuaciones $k(k-1)=102-(16+2)=84=12\cdot7$ $k(k-1)=102-(16-2)=88=11\cdot8$ no tienen soluciones.

Para $h=2$, la ecuación de $k(k-1)=102-(64+4)=34=17\cdot2$ no tiene soluciones, pero la ecuación de $k(k-1)=102-(64-4)=42=7\cdot6$ tiene un único (positivo) de la solución.

Desentrañar esta, tenemos $n=2k-1=13$$m=8h=16$, por lo que el $(2m-1)^2+(2n)^2=31^2+26^2$ es la única representación de $1637$ como la suma de dos cuadrados. Por lo tanto $1637$ es primo.