- #1
QIsReluctant
- 37
- 3
Hello,
The following problem appears in my number theory text:
The answer:
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.
The following problem appears in my number theory text:
Show that if n=161038, then n divides 2n - 2.
The answer:
It is easy to verify that n = 2 * 73 * 1103 and n - 1 = 32 * 29 * 617. Hence 2n-1 - 1 is divisible by 29 - 1 = 7 * 73 and by 229 - 1, which in turn is divisible by 1103. This is done more or less by brute force: 210=-79 mod 1103, so 220=726 mod 1103, and 229= 1 mod 1103. So 2n - 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.