Divisibility of large number

Question

This was a question asked in a competitive exam:

$(300^{3000} -1 )$ is divisible by

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

The answer is $301$. Not sure how they arrived at the answer. Can somebody explain ?

Answer 1

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

Answer 2

Let us consider the polynomial $x^n-1$ where $n$ is even, then $-1$ is a root of the polynomial and so it is divisible by $x-(-1)=x+1$. Put $x=300,n=3000$ to get the answer.

Answer 3

An alternative to Dan's answer: $300 \equiv -1 \pmod{301}$, and $(-1)^{5 \cdot k} \equiv -1 \pmod{301}$. Now $$ 300^{3000} - 1 = (300^{1500}+1)(300^{1500}-1)=(300^{1500}+1)(300^{750}+1)(300^{375}+1)(300^{375}-1), $$ so $$ (300^{375}+1) \equiv (300^{5\cdot 75}+1) \equiv 0 \bmod 301 $$

Answer 4

This answer only expands on Dan Brumleve's.

What is a Congruence relation?

Given two integers $x, y$. The statement that $x − y$ is divisible by another integer $k$ is equivalent to saying that the $x$ is congruent to $y$ modulus $n$, and written in the congruence notation as $x \equiv y\ (\textrm{mod}\ k)$ or equivalently as $k | (x - y)$.

The congruence relation has the following properties:

If both

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

hold then these three properties must hold

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)$ and
   $a_2^t \equiv b_2^t (\textrm{mod}\ m)$ (Property 10 from Wolfram's list).

It is not hard to show that Property 3 follows from Property 2, but we won't go there at this time.

Restatement in terms of congruence relation

Your original question can then be restated as follows:

If $300^{3000} - 1 \equiv 0 (\textrm{mod}\ n)$, what is $n$ from the list?
a) 401 b) 501 c) 301 d) 901

Dan's Solution Expanded

$300^{3000} - 1 \equiv 0 (\textrm{mod}\ n)$ can be rewritten as

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

But each of the following two expressions is trivially true for $n=301$:

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

By Property 4, these two also follow:

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

Simplified the above becomes:

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

By the Property 2 (subtraction rule), we can put these two together to obtain:

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

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)= ... so 299 and 301 are definely divisors of (300^3000−1)