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

-
That it is divisible by 301 can be seen by looking at it mod 301 where it becomes $(-1)^{3000} - 1 = 1- 1 = 0$. That it is not divisible by the other numbers is not as easy to see, but I assume this was not a test where multiple answers could be correct. – Tobias Kildetoft Jul 16 '12 at 10:02
300^3000 -1 is in the form x^n -1 which id divisible by x-1 so it is divisible by 300-1 that is 299. – user35970 Jul 17 '12 at 7:40
@priti: The question asked which of the following is a divisor of $300^{3000}-1$, your answer - $299$ - does not appear on that list. – Asaf Karagila Jul 17 '12 at 9:51

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

-

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.

-
It's wrong: $(300+1)|300^{1500}\color{red}-1$. And even then this only reduces the problem. $301$ also divides $300^{750}-1$... – draks ... Jul 16 '12 at 10:11
Sorry for the mistake, hope I have corrected it. – pritam Jul 16 '12 at 10:22
+1 Look's fine now. – draks ... Jul 16 '12 at 10:34
Hi, can you elaborate on the "..then −1 is a root of the polynomial and so it is divisible by x−(−1)=x+1". I did not understand this. – user2434 Jul 16 '12 at 10:52
@user2434 just set $x=-1$. You see that it's a root $(-1)^n -1 =0$. When you know a root $a$, you can divide your polynomial by $x-a$, so $x-(-1)|x^n-1$. – draks ... Jul 16 '12 at 10:57

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^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)

-
The problem here is the "..." bit. Although 3000, 1500 and 750 are even, and so allow you to use the difference of two squares, 375 is odd, and so there is no next step in this sequence. – tttppp Jul 18 '12 at 7:23
-1 Does not answer the question. Consider withdrawing your answer. – rrufai Aug 1 '12 at 11:48

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

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

-

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.

-