Question

For any n, 33 divides (n^101-n). Prove this is true.

Answer 1

There's a solution given and it gives the hint that you want to prove "n\[n^{100}\approx n(mod 33)\]. I'm using the \[\approx\] for "congruent to".

There's a solution which I partially understand. The only step confusing me is at the beginning is when they say:
From Fermat's theorem, \[n ^{2}\approx1(mod 3) => n ^{3}\approx n(mod 3)\]
and \[n ^{10}\approx1(mod 11) => n ^{11}\approx n(mod 3)\]

How would this be true for EVERY n (as stated initially) since Fermat's theorem only works if \[p\] doesn't divide \[a\] (where p is prime) in \[a ^{p-1}\approx1(\mod p)\]

Answer 2

Oops I made a mistke, it should be n^11 = n (mod 11) ... not mod 3!

Answer 3

kirby p is the exponent, not n

Answer 4

n can be anything at all

Answer 5

but wouldn't it have to be in this case that 3 doesn't divide n
and that 11 doesn't divide n ? Wouldn't this not work if n was a multiple of 3 or 11 respectively

Answer 6

oooh i see

Answer 7

but it is trivially true if p divides n

Answer 8

if p divides n then n^p is a multiple of p, but is certainly congruent to n mod p because n mod p is 0

Answer 9

for example 3 divides 9 and 3^9=27 congruent to 9 mod p congruent to 0 mod p

Answer 10

i have never seen fermat's little theorem stated that n and p had to be relatively prime. just looked it up on wiki and it doesn't say that either

Answer 11

hm weird, my book clearly stated it o_O And they said the same for the more general Euler's theorem.
But I guess I'll take your word for it :)

Answer 12

hold on. if p divides n, then n is congruent to n mod p because n mod p is 0

Answer 13

There are 2 formulations of FLT

1) a^(p-1) = 1 mod p with gcd(a,p)=1 OR

2) a^p = a mod p if p is a prime and a any integer.

Answer 14

@kirby you are trying to prove that for any n, 33 divides
\[n^{101}-n\]

if 33 already divides n you have nothing to prove because if it divides n it certainly divides
\[n^{101}-n\]

Answer 15

so you have no worries in that case. it is true before you start

Answer 16

Ohh! Haha oh my , that should've been obvious from the start :( Haha thanks a lot :)

Answer 17

Oh but wait! I think I'm getting confused! How do we know 33 divides n from the start?

Answer 18

Ohh ok I see from estudier's post that the condition that (a, p)=1 is "removed" if you state it as a^p = a (mod p)... That was not really said in my book, or I didn't catch that.. Ok now it makes sense :)