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

-

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

-

(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