proof for divisibility

Question

Prove without the use of congruences that $341$ divides $2^{340} - 1$. This was a question I found in a book right after which Fermat's little theorem is discussed. I tried using it for the proof but turns out $341$ isn't even prime. Any help would be appreciated.

Answer 1

A way to do this is to note $2^{10}-1 \mid 2^{340}-1$ as $10 \mid 340$.

Then $2^{10}-1 = (2^5 -1)(2^5 +1)$. The former is $31$ the latter $33$, so that their product is certainly divisible by $31 \cdot 11= 341$.

(It is not quite clear to me if this is the intended solution.)

Answer 2

We have $341=11\cdot 31$, so we have to prove that both $31$ and $11$ divides $2^{340}-1$

We know that : $11$ divides $x^{10}-1$ for every $x$ coprime to $11$, let's take $x=2^{34}$, hence $11$ divides $2^{340}-1$

Using the same argument $31$ divides $2^{30*11}-1$ for every and we know that: $$2^{340}-1=2^{330}(1024)-1=1024(2^{330}-1)+1023=1024(2^{330}-1)+31\cdot33 $$ hence $31$ divides $2^{340}-1$

As a conclusion we have $341$ divides $2^{340}-1$