Divisibility of large number 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 ?
 A: 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.
A: 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
$$
A: $300 \equiv -1 \pmod{301}$, and $(-1)^{2 \cdot k} \equiv 1 \pmod{301}$, so $300^{2 \cdot 1500} - 1 \equiv 0 \pmod{301}$.
A: 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 $k$, 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

*

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

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

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

*$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)$

A: (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) 
A: One relies on Fermats little theorem, which says if $p$ is a prime, then it divides $x^p-x$ for all integer $x$.  Of course, it can divide for smaller values, where $p \not\mid x$, then $p \mid x^{p-1}-1$, and where $p \mid x^m-1$, then $m \mid p-1$.  
The second instance is that for particular values of $x$, $p \mid x^s -1$, where $s \mid p-1$.  For example, where p=37, x=10, one can have s=3, rather than s=36.
For $301  = 7 \cdot 43$, we see that $7-1 \mid 3000$, and $6$ is the largest number to divide both 42 and 3000.  So all we have to see is whether 43 divides 299, 301, 27000001, or 26999999.  It divides 301, so this one does divide.
For $401 = \mbox{prime}$, we see that $400 \not\mid 3000$, but we need to eliminate the possibilities.  Gauss's law of quadratic residues tells us that there is no solution to $x=3 \pmod 401$, so whatever the period of $401$ is in base 300, it does not divide 3000. Therefore we exclude this.
For $501 = 3 \cdot 167$.  Two multiples of 3 can not be one apart, so if $3 \mid x$, then $3 \not\mid x-1$.  
For $901 = 17 \cdot 53$, we need to test both 17 and 53.  However, because the period of 1/17 in base 300 is 16, we see that $16 \not\mid 3000$, and hence $17$ does not divide the number.  One can show also that If 53 divides the number, it must divide 90001, which yields negative results under simple arithmetic.
