Intereting Posts

A bounded net with a unique limit point must be convergent
$\pi$ from the unit circle, $\sqrt 2$ from the unit square but what about $e$?
Product of all elements in finite group
Prove that $x\sqrt{1-x^2} \leq \sin x \leq x$
Where, specifically, did Principia Mathematica fail?
Can you multiply two vectors $v$ and $u$ using multiplication instead of dot or cross products
Mathematical problem induction: $\frac12\cdot \frac34\cdots\frac{2n-1}{2n}<\frac1{\sqrt{2n}}$
Why can't Fubini's/Tonelli's theorem for non-negative functions extend to general functions?
Why don't analysts do category theory?
Complex Polynomial with roots in uppar half plane.
Basis for the set of all covariant $k$-tensors on V
Infinite set always has a countably infinite subset
This is a possible proof of the Riemann Hypothesis
For integers $a\ge b\ge 2$, is $f(a,b) = a^b + b^a$ injective?
Treacherous Euler-Lagrange equation

For $m>2$, if a primitive root modulo $m$ exists, prove that the only solutions of the congruence $x^2 \equiv 1 \pmod m$ are $x \equiv 1 \pmod m$ and $x \equiv -1 \pmod m$.

Thanks.

- Is there a finite number of $(a, b)$ pairs that satisfy, ${a+b} \leq \frac {{a^2}b+{b^2}a}{a^2 +b^2}$
- Is it always true that if $\gcd(a,b)=1$ then $\gcd(ab, c) = \gcd(a, c)\gcd(b, c)$?
- Is $a^b+b^a$ unique for all integers a and b?
- Discriminant of a binary quadratic form and an order of a quadratic number field
- Greatest common divisor of $3$ numbers
- What five odd integers have a sum of $30$?

- How can I prove that $n^7 - n$ is divisible by $42$ for any integer $n$?
- $p$-Splittable Integers
- Somos 3 Sequence
- Summation involving totient function: $\sum_{d\mid n} \varphi(d)=n$
- If $a,b$ are positive integers such that $\gcd(a,b)=1$, then show that $\gcd(a+b, a-b)=1$ or $2$. and $\gcd(a^2+b^2, a^2-b^2)=1$ or $2 $
- Sum and difference coprimes
- Sum of Positive Divisors: $\sum_{d|n} \mu(n/d)\nu(d)=1$ and $\sum_{d|n} \mu(n/d)\sigma(d)=n$
- Nested Division in the Ceiling Function
- The product of n consecutive integers is divisible by n factorial
- An infinitude of “congruence condition” primes?

Here is an indirect solution – a solution that doesn’t use any specific primitive root. I think a better solution exists, but I would still like to post it because it gives a different perspective.

The solutions $1$ and $m-1$ are obviously always solutions. So the difficulty is proving there aren’t any more.

By the primitive root theorem, the possibilities for $m$ are $m=2$, $m=4$, $m=p^k$, or $m=2p^k$ where $p$ is an odd prime and $k\ge 1$.

For $m=2$ we actually have $1=m-1$, and there is a *unique* square root of $1$.

For $m=4$ you may check directly that the claim holds, just by calculating.

For $m=p^k$, we prove by induction on $k$. For $k=1$ there are no zero divisors, so $(x-1)(x+1)=0$ implies $x-1=0$ or $x+1=0$. For $k>1$, assuming there are exactly two solutions modulo $p^{k-1}$, we use Hensel’s lemma to claim that these lift to exactly two solutions modulo $p^k$.

For $m=2p^k$ we use the Chinese remainder theorem to combine the two solutions modulo $p^k$ with the unique solution modulo $2$ to get two solutions modulo $m$.

$x^2$$\equiv$1 mod m means that m|($x^2$-1)…..what can you infer from this?

Here is a direct solution involving a primitive root (see also my other answer for an “indirect” solution):

Let $r$ be a primitive root modulo $m$ and let $\{r^0, r^1, \ldots, r^s\}$ be the multiplicative group mod $m$.

Let $x$ satisfy $x^2 = 1$. Then $x$ must be a member of the multiplicative group, since it’s invertible mod $m$ (it is its own inverse). So we can write $x = r^k$ for some integer $k$, and we know that $r^{2k} \equiv r^0 \pmod m$. This gives us $2k \equiv 0 \pmod {\phi(m)}$ where $\phi$ is Euler’s totient function. This congruence has at most two solutions (this I leave as exercise), giving at most two solutions for $x$.

Suppose $\,w\,$ is a primitive root modulo $\,m\,$ , and $\,x=w^k\,$ , then

$$x^2=1\pmod m\iff w^{2k}=1\pmod m\iff$$

$$ (w^k-1)(w^k+1)=0\pmod m\iff (x-1)(x+1)=0\pmod m\ldots$$

The fact that *any* unit $\,x\,$ modulo $\,m\,$ is a power of $\,w\,$ follows from the fact of the latter being a *primitive* root modulo $\,m\,$…If $\,m\,$ has no primitive roots then the claim isn’t true.

**Warning:** In the last step you *still* have to give a very little explanation…

hint: an equation of degree 2, also in modular arithmetic, has at most two solutions if a primitive root modulo $m$ exists

- Counting Irreducible Polynomials
- Prove that if $\sum{a_n}$ converges absolutely, then $\sum{a_n^2}$ converges absolutely
- how many terms will there be once you collect terms with equal monomials? What is the sum of all the coefficients?
- A prime number random walk
- Perfect set without rational numbers
- Trisect unknown angle using pencil, straight edge & compass; Prove validity of technique
- Explicitly proving invariance of curvatures under isometry
- How discontinuous can a derivative be?
- $\lim_{n\rightarrow \infty } (\frac{(n+1)^{2n^2+2n+1}}{(n+2)^{(n+1)^2}\cdot n^{n^2}})$
- An irreducible polynomial in a subfield of $\mathbb{C}$ has no multiple roots in $\mathbb{C}$
- Block inverse of symmetric matrices
- Prove a certain property of linear functionals, using the Hahn-Banach-Separation theorems
- What is this pattern called?
- How can a social welfare function be a linear combination of von Neumann-Morgenstern utility functions?
- Does a dense $G_\delta$ subset of a complete metric space without isolated points contain a perfect set?