Number Theory: Unclear Explanation of Divisibility Question

[QIsReluctant]

Hello,

The following problem appears in my number theory text:

Show that if n=161038, then n divides 2ⁿ - 2.

The answer:

It is easy to verify that n = 2 * 73 * 1103 and n - 1 = 3² * 29 * 617. Hence 2^n-1 - 1 is divisible by 2⁹ - 1 = 7 * 73 and by 2²⁹ - 1, which in turn is divisible by 1103. This is done more or less by brute force: 2¹⁰=-79 mod 1103, so 2²⁰=726 mod 1103, and 2²⁹= 1 mod 1103. So 2ⁿ - 2 is divisible by 2, 73, and 1103, and hence it is divisible by n.

I have tried to trace the reasoning in reverse. I understand how we get to the finish (by showing that the number is divisible by all of the relatively prime factors of n, but I don't understand how we actually show divisibility by those factors. Can someone show me the light? This chapter is on the theorems of Fermat, Wilson, and Euler.

 

[QIsReluctant]

No responses? Do I need to give some more information?