Number Theory Question?

i think you must have made some mistake in stating your problem.

for example, (2,17) = 1, but

2^16 - 1 = 65,535 is odd, and certainly not divisible by 2.

similarly, 5^16 - 1 ends in 4 (as all powers of 5 end in 5), and therefore is not divisible by 5.

i believe what you MEANT to say, is that if (n,17) = 1 that

n^16 - 1 is divisible by 17.

this is a case of "Fermat's Little Theorem" which says that

n^(p-1) = 1 (mod p), if p does not divide n.

to see this form the following (p-1) multiples of n:

n,2n,3n,....(p-1)n

i claim these are all distinct (mod p).

suppose sn = tn (mod p), 1 ≤ s, t ≤ p-1

then (s - t)n = 0 (mod p). since (n,17) = 1

s - t = 0 (mod p), whence s = t.

thus

n(2n)(3n)....(p-1)n = 1(2)(3)....(p-1) (mod p)

so (p-1)!n^16 = (p-1)! (mod p)

thus n^16 = 1 (mod p) or, equivalently:

n^16 - 1 = 0 (mod p)

which is to say n^16 - 1 is a multiple of p.

The (best) way to solve it is by Fermat's Little Theorem. But since you don't want to solve it that way, the only way left is by Quotient Remainder Theorem

For all integers, n

n = 17k, 17k + 1, 17k + 2, 17k + 3, 17k + 4, 17k + 5, 17k + 6, 17k + 7, 17k + 8, 17k + 9, 17k + 10, 17k + 11, 17k + 12, 17k + 13, 17k + 14, 17k + 15, 17k + 16

substitute each of the following values of n into n^16 - 1 and factorizing it shows that 17 is definitely a factor for all cases. So n^16 - 1 is divisible by 17.

So you just want to show that n^17 - n is divisible by 17 for all n.

By induction 1^17 - 1 = 0. Then by binomial expansion

(n+1)^17 - (n+1) = 1 + 17*n +(17C2)n^2+.....+(17C16)n^16 + n^17 - n - 1

= n^17 - n + 17(n + .........+n^16), the point being that for all k in[1,16], 17Ck is a multiple of 17 since 17 is prime.

So if n^17 - n is a muliple of 17, so is (n+1)^17 - (n+1). Ok?

Look up Fermat's Little Theorem.

This uses eulers theorem.

where a^phi(n)=1 mod n

where (a,n)=1.

So for your question, n=17 and phi(17)=16.