2024/013) Prove that $123123 | 2^{60}-1$

To show that 123123 is a factor of $2^{60}-1$ we need to show that each prime factor of 123123 to the highest power is a factor

Now let us factor 123123

$123123= 123 * 1001 = 3 * 41 * 7 * 11 * 13$ 

As each prime occurs once we need to prove each of 3,7,11,13,41 divides  $2^{60}-1$

We know $x^y-1 | x^{my}-1$ for any m

We have $2^2-1 |  2^{60}-1$  and $3| 2^{2} -1$ using FLT(Fermat's Little Theorem)  so $3| 2{60}^-1$

$2^6-1 |  2^{60}-1$  and $7| 2^{6} -1$ using FLT(Fermat's Little Theorem)  so $7| 2{60}^-1$

$2^{10}-1 |  2^{60}-1$  and $11| 2^{10} -1$ using FLT(Fermat's Little Theorem)  so $11| 2{60}^-1$

 $2^{12}-1 |  2^{60}-1$  and $13| 2^{12} -1$ using FLT(Fermat's Little Theorem)  so $13| 2{60}^-1$

Now we need to prove for 41

using FLT we know  $41| 2^{40} -1$

So let us find $GCD(2^{(60}-1,2^{40}-1)$

$GCD(2^{(60}-1,2^{40}-1)= GCD((2^{(60}-1) - (2^{40-1},2^{40}-1)$

$=GCD((2^{60} - 2^{40}), 2^{40}-1)$

$=GCD((2^{40}( 2^{20}-1), 2^{40}-1)$

 $=GCD((2^{20}-1), 2^{40}-1)$ as second number is odd so removing even factors of 1st number

$= 2^{20}-1$ as this is a factor of  $2^{40}-1$

now $= 2^{20}-1)= (2^{10}-1)(2^{10}+1)$

$=  1023 * 1025$ as $41 | 1025$ so $41 | 2^{60}-1$

as each of 3,7,11,13,41 divides  $2^{60}-1$ so 123123 is a factor