/sci/ - Science & Math

[Anonymous No.1224045]

ITT: We prove Fermat's little theorem.

[Anonymous No.1224052]

The first is that we may assume that a is in the range 0 ≤ a ≤ p − 1. This is a simple consequence of the laws of modular arithmetic; we are simply saying that we may first reduce a modulo p.

Secondly, it suffices to prove that

a^{p-1} \equiv 1 \pmod p \quad \quad (X)

for a in the range 1 ≤ a ≤ p − 1. Indeed, if (X) holds for such a, then we can simply multiply both sides by a to obtain the original form of the theorem,

a^p \equiv a \pmod p, \,\!

and if a happens to be zero, the original equation in its original form is obviously true anyway.

/thread

[Anonymous No.1224053]

little theorem is small time

[Anonymous No.1224065]

Let <span class="math"> Z_p [/spoiler] be the integers modulo p under multiplication.

Then for some <span class="math"> a \in Z_p [/spoiler] let k be the order of a, i.e

<span class="math"> a^k \equiv 1 \pmod p [/spoiler]

..

[Anonymous No.1224068]

How about we prove fermat's theorem with eucledian mathematics

[Anonymous No.1224075]

>>1224065
yeah but don't forget the case p divides a

[Anonymous No.1224080]

>>1224065

Then by Lagrange's Theorem, k divides the order of the group, i.e km=p-1 for some m.
Then

<span class="math"> a^{p-1} \equiv a^{km} \equiv (a^k)^m \equiv 1^m \equiv 1 \pmod p[/spoiler]


done.

[Anonymous No.1224086]

i love the little theorem! it's one of my favorites, though i rarely get to use it.

[Anonymous No.1224101]

phi(p)=p-1 where phi is eulers totient, also, gcd(a,p)=1 if p does not divide a. so we first prove this theorem for the case where a does not divide p. then by eulers theorem, a^phi(p)= a^p-1 = 1 (mod p), so a^p = a (mod p).
next, if p divides a then a = 0 = 0^p = a^p mod p.

[Anonymous No.1224312]

the first proof of the theorem i experienced was one that i constructed myself. i proved it by induction.
first i showed that p divides p choose k for all 0<k<p, and i assume this was done by using euclids lemma on the fact that the denominator of the product expansion of p choose k (which is k! coprime to p) divides the numerator, which contains p times another number.
next i showed that (a+b)^p = a^p + b^p (mod p) by expanding the left side of this equation using the binomial theorem, achieving a^p + (a bunch of terms which have p choose k as a factor, so p divides all these terms) + b^p = a^p + 0 + b^p.
next, 0^p = 0 (mod p), and if n^p = n (mod p), then (n+1)^p = n^p + 1^p = n + 1 (mod p), proving the theorem by induction for all non-negative integers.
finally, if p is an odd prime, and a is negative, then a^p = (- -a)^p = -(-a)^p = -(-a) = a (mod p), and the case where p=2 is trivial.

[Anonymous No.1224364]

Ok heres another way

let me see here,

x^n + y^n /= z^n , n>2

prove true for n=3

x^3 + y^3 /= z^3
....must be true

x^(k+1) +y^(k+1) /= z^(k+1)

but original hypothesis states for k
therefore

x^1 + y^1 = z^1

so for x=1 y =2 , z must equal 3
which was in the initial hypothesis (x^3 +y^3 = z^3) which wasn't true therefore its not true or k+1

[Anonymous No.1225204]

multiplication by a unit a mod p permutes the unit set of Z/pZ (call this Up), so the product of all the elements of Up (call this A) and the product of all the elements in aUp are equal, and since Up has p-1 elements, A=Aa^p-1. since A is a unit, a^p-1=1 (mod p) for units a, and this is obviously equivalent to fermats little theorem. a similar argument can be used to prove eulers theorem.

[Anonymous No.1225234]

>>1224080
you would have to prove that the units mod p are cyclic. i bet you could do that by exhibiting the existence of primitive roots mod p. actually it should follow really easily from that.