Intereting Posts

Ramanujan-type trigonometric identities with cube roots, generalizing $\sqrt{\cos(2\pi/7)}+\sqrt{\cos(4\pi/7)}+\sqrt{\cos(8\pi/7)}$
Solution to $x^n=a \pmod p$ where $p$ is a prime
Express this sum of radicals as an integer?
A PDE exercise from Gilbarg Trudinger. problem 2.2
Formula for a periodic sequence of 1s and -1s with period 5
A and B are nxn matrices, $A =B^TB$. Prove that if rank(B)=n, A is pos def, and if rank(B)<b, A is pos semi-def.
dimension of a subspace spanned by two subspaces
Prove that $|\log(1 + x^2) – \log(1 + y^2)| \le |x-y|$
Let $f$ be a bounded measurable function on $E$. Show that there are sequences of simple functions converging uniformly on $E$.
Mathematical symbol for “and”
Number of solutions of $x^2_1+\dots+x^2_n=0,$ $x_i\in \Bbb{F}_q.$
Let $a,b$ be positive integers such that $a\mid b^2 , b^2\mid a^3 , a^3\mid b^4 \ldots$ so on , then $a=b$?
Transformation of state-space that preserves Markov property
Explanation of proof of Gödel's Second Incompleteness Theorem
Show that $\mathbb{Q}(6^{1/3})$ and $\mathbb{Q}(12^{1/3})$ have the same degree and discriminant but are not isomorphic.

What is the purpose of using Fermat’s Little Theorem, and a proof of it?

- calculating nested exponents modulo n
- Rational points on $y^2 = 12x^3 - 3$.
- Pure Mathematics proof for $(-a)b$ =$-(ab)$
- Prove or disprove that $\exists a,b,c\in\mathbb{Z}_+\ \forall n\in\mathbb{Z}_+\ \exists k\in\mathbb{Z}_+\colon\ a^k+b^k+c^k = 0(\mathrm{mod}\ 2^n)$
- The equation $x^n+y^n+z^n=u^n+v^n+w^n=p$, where $p$ is prime.
- Positive Integers Equation
- A fast factorization method for Mersenne numbers
- Does there exist a computable number that is normal in all bases?
- Find the value of $\left$
- Knight move variant: Can it move from $A$ to $B$

Below is what Weil wrote on proofs of Fermat’s little theorem, from p. 56 of his *Number theory: An approach through history*. As for its purpose, it helps serve to reveal the multiplicative structure of $\rm\:\mathbb Z/p\:,\:$ and problems in $\rm\:\mathbb Z\:$ are often best solved by reducing them to much simpler problems in its finite images $\rm\:\mathbb Z/p\:,\:$ e.g. so-called “local-global” principles. No doubt a search on “Fermat little” will uncover many applications – both here and elsewhere.

In modular arithmetic e.g. mod m you can reduce big numbers down to numbers between 0 and m.

Fermat’s little theorem lets you reduce the exponents (of numbers of the form $b^e$) down to numbers between 0 and $\varphi(m)$ (without knowing anything about the base).

For example of the first, $x = 0,1,2$ or $3$ mod 4 so the number $x^2$ must be equal to 0 or 1 mod 4. So $x^2$ is of the form 4k or 4k+1.

For an example of the second, if p is prime $\varphi(p) = p-1$ then $p^2 = 1$ mod p-1 so $x^{(p^2)} = x$ mod p. I just made that up but you can probably see from it that you can use this for lots of things.

We prove by fermat’s little theorem by induction. Firstly, the base case tells us that

$1^{p} \equiv 1$ (mod $p$), which is true.

Assume true for $a=k$, namely that we assume $k^{p} \equiv k $ (mod $p$).

Then for $a = k+1$, we observe that $(k+1)^p – (k^p +1) = pk$ + $p \choose 2$ $k^2$ + $\ldots$ $k^{p-1}$ $p\choose p-1$.

I leave it as an exercise to check that the R.H.S. is divisible by $p$, and so we have the chain of congruences (using the induction hypothesis) that $(k+1)^p \equiv k^p + 1 \equiv k+1 $ (mod $p$). So the statement of fermat’s little theorem is true for $a = 1$, $a = k$ and $a = k+1$ and hence is true for all natural numbers $k$.

$\hspace{6in}\blacksquare$

Ben

Fermat’s little theorem states that, for a prime $p$:

$$ a^p \equiv a \pmod{p} $$

alternatively:

$$ a^{p-1} \equiv 1 \pmod{p} $$

The easiest proof that I’ve seen is as follows: Consider *any* integer, $g$, that is relatively prime to $p$. Let $x$ be the product of all of the (distinct) integers $\pmod{p}$. i.e.:

$$ x = 1 \cdot 2 \cdot 3 \dots (p-1) \pmod{p} $$

Now, multiply each term on the right by $g$:

$$ g^{p-1} x = (g \cdot 1) (g \cdot 2) (g \cdot 3) \dots (g \cdot (p-1)) \pmod{p} $$

Since multiplication is 1-1 and onto, all this does is permute the values involved in the product on the right to give back $x$. So:

$$ g^{p-1} x = x \pmod{p} $$

$$ g^{p-1} = 1 \pmod{p} $$

One needs to prove multiplication is 1-1 and onto (for $p$ prime), but once that’s done, the proof above is (in my opinion) straight forward and simple.

EDIT: I originally restricted the product, $x$, to be the product of powers of a generator, $g$. As lhf points out, this can be any number. I’ve changed the above to reflect this.

- If $R$ is a commutative ring with unity and $R$ has only one maximal ideal then show that the equation $x^2=x$ has only two solutions
- Prove that there does not exist integer solutions for the diophantine equation $x^5 – y^2 = 4$.
- What are the theorems of mathematics proved by a computer so far?
- Proving a shifting inequality
- If $f \circ g$ is onto then $f$ is onto and if $f \circ g$ is one-to-one then $g$ is one-to-one
- Is the expected value of a random variable always constant?
- Do infinitely many points in a plane with integer distances lie on a line?
- How to entertain a crowd with mathematics?
- Determining the Asymptotic Order of Growth of the Generalized Harmonic Function?
- On the root systems
- Why does the Pythagorean Theorem have its simple form only in Euclidean geometry?
- Prove that $\lim_{n\to\infty}a_n\le \lim_{n\to\infty}b_n$
- Show that the set of all infinite subsets of $\mathbb{N}$ has cardinality greater than $\mathbb{N}$
- Lebesgue Integral of a piecewise defined function defined on irrationals and rationals(GATE-2017)
- Define the image of the function $f :\Bbb Z \times \Bbb N →\Bbb R$ given by $f(a, b) = \frac{a−4}{7b}$?