La divisibilidad de un gran número de

Question

Esta fue una pregunta en un examen competitivo:

$(300^{3000} -1 )$ es divisible por

a) $401$ b) $501$ c) $301$ d) $901$

La respuesta es $301$. No está seguro de cómo llegaron a la respuesta. Puede alguien explicar ?

Answer 1

$300 \equiv -1 \pmod{301}$, e $(-1)^{2 \cdot k} \equiv 1 \pmod{301}$, lo $300^{2 \cdot 1500} - 1 \equiv 0 \pmod{301}$.

Answer 2

Una alternativa a Dan la respuesta: $300 \equiv -1 \pmod{301}$, e $(-1)^{5 \cdot k} \equiv -1 \pmod{301}$. Ahora $$ 300^{3000} - 1 = (300^{1500}+1)(300^{1500}-1)=(300^{1500}+1)(300^{750}+1)(300^{375}+1)(300^{375}-1), $$ así $$ (300^{375}+1) \equiv (300^{5\cdot 75}+1) \equiv 0 \bmod 301 $$

Answer 3

Esta respuesta sólo se expande en Dan Brumleve.

¿Qué es una relación de Congruencia?

Dados dos enteros $x, y$. La declaración de que $x − y$ es divisible por otro número entero $k$ es equivalente a decir que el $x$ es congruente a $y$ módulo de $k$, y escrito en la congruencia de la notación, $x \equiv y\ (\textrm{mod}\ k)$ o, equivalentemente, como $k | (x - y)$.

La congruencia relación tiene las siguientes propiedades:

Si ambos

$a_1 \equiv b_1 (\textrm{mod}\ m)$ y
$a_2 \equiv b_2 (\textrm{mod}\ m)$

mantenga a continuación, estas tres propiedades debe poseer

1. $a_1 + a_2 \equiv b_1 + b_2 (\textrm{mod}\ m)$
2. $a_1 - a_2 \equiv b_1 - b_2 (\textrm{mod}\ m)$
3. $a_1 a_2 \equiv b_1 b_2 (\textrm{mod}\ m)$
4. $a_1^s \equiv b_2^s (\textrm{mod}\ m)$ y
   $a_2^t \equiv b_2^t (\textrm{mod}\ m)$ (Propiedad de 10 de Wolfram de la lista).

No es difícil mostrar que la Propiedad 3 se sigue de la Propiedad 2, pero no vamos a ir allí en este momento.

Reformulación en términos de congruencia relación

Su original pregunta puede ser reformulada de la siguiente manera:

Si $300^{3000} - 1 \equiv 0 (\textrm{mod}\ n)$, lo $n$ de la lista?
a) 401 b) 501 c) 301 d) 901

Dan la Solución Ampliado

$300^{3000} - 1 \equiv 0 (\textrm{mod}\ n)$ puede escribirse como

$(300^{2\cdot1500} - 1^{2\cdot 1500}) \equiv 0 (\textrm{mod}\ n)$

Pero cada una de las dos expresiones siguientes es trivialmente cierto para $n=301$:

$300 \equiv -1 (\textrm{mod}\ n)$ desde $301 | 300 - (-1)$
$1 \equiv 1 (\textrm{mod}\ n)$ desde $301 | 1 - 1$.

Por la Propiedad 4, estos dos también sigue:

A. $300^{2\cdot1500} \equiv (-1)^{2\cdot1500} (\textrm{mod}\ 301)$
B. $1^{2\cdot1500} \equiv 1^{2\cdot1500} (\textrm{mod}\ 301)$

Simplificada de la anterior se transforma en:

A. $300^{2\cdot1500} \equiv 1 (\textrm{mod}\ 301)$
B. $1 \equiv 1 (\textrm{mod}\ 301)$

Por la Propiedad 2 (regla de la resta), podemos poner a estos dos juntos para obtener:

$(300^{2\cdot 1500} - 1) \equiv 0 (\textrm{mod}\ 301)$

Answer 4

Consideremos el polinomio $x^n-1$ donde $n$ es incluso, a continuación, $-1$ es una raíz del polinomio y así es divisible por $x-(-1)=x+1$. Poner $x=300,n=3000$ para obtener la respuesta.

Answer 5

(a^2-b^2)=(a+b)(a-b)

300^3000-1=300^3000-1^3000=(300^1500-1^1500)(300^1500+1^1500)= =(300^750-1^750)(300^750+1^750)(300^1500+1^1500)= =((300^375-1^375)(300^375+1^375)(300^750+1^750)(300^1500+1^1500)= ... así 299 y 301 se definely divisores de (300^3000-1)