Intereting Posts

How to read negative radians in the interval?
Proving $\gcd( m,n)$=1
Variation under constraint
Primes between $n$ and $2n$
Which step in this process allows me to erroneously conclude that $i = 1$
Lower Semicontinuity Concepts
What are zero divisors used for?
A nontrivial subgroup of $G$ contained in every other nontrivial subgroup.
$\tau$ and grouping of prime numbers
Find the common divisors of $a_{1986}$ and $a_{6891}$
Approximating indicator function on open set continuous functions
Reformulation of Goldbach's Conjecture as optimization problem correct?
Why does “convex function” mean “concave *up*”?
If the dot product between two vectors is $0$, are the two linearly independent?
Proving $\mathrm e <3$

If $a^{N-1} \neq 1\pmod{N}$ for some $a$ relatively prime to $N$, then must the equality fail for at least half the choices of $a<N$

Could someone provide proof for this statement?

- The number of genera of binary quadratic forms of given discriminant
- Some hints for “If a prime $p = n^2+5$, then $p\equiv 1\mod 10$ or $p\equiv 9\mod 10$”
- If $a$, $a+2$ and $a+4$ are prime numbers then, how can one prove that there is only one solution for $a$?
- 3 never divides $n^2+1$
- Diophantine equation $a^2+b^2=c^2+d^2$
- If a and b are relatively prime and ab is a square, then a and b are squares.

- Elementary central binomial coefficient estimates
- If $\gcd(m,n)=1$, find $\gcd(m+n,m^2-mn+n^2)$?
- Numbers $p-\sqrt{q}$ having regular egyptian fraction expansions?
- how to calculate double sum of GCD(i,j)?
- What is wrong with this proof that there are no odd perfect numbers?
- Number of integer triplets $(a,b,c)$ such that $a<b<c$ and $a+b+c=n$
- When is the sum of divisors a perfect square?
- How do I prove that 15462227 and 15462229 relatively prime?
- Division of Factorials
- How many digits does $2^{1000}$ contain?

The proof is in the Wikipedia article on the Fermat primality test.

[*Edit in response to the comment:*]

The proof in more detail: If $N$ is composite, a number $a$ is called a *Fermat witness* for $N$ if $a^{N-1} \not\equiv1\pmod N$, and a *Fermat liar* if $a^{N-1}\equiv1\pmod N$. Given $N$, let $a$ be a Fermat witness coprime to $N$, and $b$ a Fermat liar (and thus also coprime to $N$). Then

$$(ab)^{N-1}\equiv a^{N-1}b^{N-1}\equiv a^{N-1}\cdot1\equiv a^{N-1}\not\equiv1\;,$$

so $ab$ is a Fermat witness. Since the residue classes $\bmod N$ coprime to $N$ form a multiplicative group (denoted by $(\mathbb Z/N\mathbb Z)^*$ in the Wikipedia article), this Fermat witness $ab$ is also coprime to $N$ and is different for every Fermat liar $b$. Thus, a single Fermat witness $a$ coprime to $N$ suffices to establish that for every Fermat liar there must be at least one Fermat witness coprime to $N$, and hence at least half of all residues $\bmod N$ coprime to $N$ (and thus also half of *all* residues $\bmod N$) must be Fermat witnesses.

- Why generalize vector calculus with $k$-forms instead of $k$-vectors?
- prove change of basis matrix is unitary
- Compatibility of topologies and metrics on the Hilbert cube
- How do you calculate the decimal expansion of an irrational number?
- Least greedy square
- Separated scheme
- The minimum perimeter and maximum height of a triangle under constraints
- cyclic three variable inequality
- Proving that $\nabla \times (U(r) \hat{r} = 0 $
- Typo: in the definition of inverse image $E$ should be replaced by $H$
- Co-equalizers in Set
- Mathematical expectation is inside convex hull of support
- Two homologous but not homotopic loops on a closed surface of genus greater than one
- Prove $\left| \int_a^b f(t) dt \right| \leq \int_a^b \left| f(t) \right| dt$
- Intuitive/Visual proof that $(1+2+\cdots+n)^2=1^3+2^3+\cdots+n^3$