Intereting Posts

Conjectured closed form of $G^{2~2}_{3~3}\left(1\middle|\begin{array}c1,1;b+1\\b,b;0\end{array}\right)$
Probability of first actor winning a “first to roll seven with two dice” contest?
What is the proper notation for integer polynomials: $\Bbb Y=\{p\in\Bbb Q\mid p:\Bbb Z\to \Bbb Z\}$?
Integral of sinc function multiplied by Gaussian
How to prove that any natural number $n \geq 34$ can be written as the sum of distinct triangular numbers?
How prove this $\sum_{k=1}^{2^{n-1}}\sigma{(2^n-2k+1)}\sigma{(2k-1)}=8^{n-1}$
Number of “passing” paths in football
Maximizing and minimizing dot products
Roots of $y=x^3+x^2-6x-7$
Proving the snake lemma without a diagram chase
Zeilbergers algorithm in Maple
What does $\propto$ mean?
improper integral $\int_{0}^{\infty } \frac{5x}{e^{x}-e^{-x}}$
Product of matrices of different order is not invertible
solve system of two trigonometric equations

I’ve just come up with this question as I’m studying for a number theory midterm. If $p$ and $q$ are different prime numbers, and it’s known that $2^p \equiv 1 \bmod{q}$, then $q\equiv 1 \bmod{p}$. I’ve tried a few cases and it seems to be true. How can it be proved?

- Proving $ \frac{\sigma(n)}{n} < \frac{n}{\varphi(n)} < \frac{\pi^{2}}{6} \frac{\sigma(n)}{n}$
- Why don't we have an isomorphism between $R$ and $ R]$?
- What's the difference between $(\mathbb Z_n,+)$ and $(\mathbb Z_n,*)$?
- Direct sum of non-zero ideals over an integral domain
- What does it mean here to describe the structure of this quotient module?
- Show that $G/H\cong S_3$
- What is a set of generators for the multiplicative group of rationals?
- Proof that every number ≥ $8$ can be represented by a sum of fives and threes.
- Polynomials and partitions
- When will a parametric solution generate all possible solutions?

**Hint** $\rm\displaystyle\,\ mod\,\ q\!:\,\ 2^p,\, 2^{q-1}\! \equiv 1 \;\Rightarrow\; 2^{gcd(p,q-1)} \equiv 1\,\Rightarrow\; gcd(\color{#c00}p,\,q\!-\!1) = \color{#c00}p\; $ (not $\color{#c00}1$ else $\rm \,q\mid 2^{\color{#c00}1}\!-1\:$)

Said in group theory language: if $\,g\ne 1$ has order dividing a prime $\,\rm p\,$ then it must have order $= \rm p.\,$ In ring theory language: if a principal ideal$\;\ne 1$ contains an irreducible element then that element generates the ideal (which is why the minimal polynomial is sometimes called the “irreducible polynomial”). $ $ Here the group / ideal is simply the so-called **order ideal** $\rm\; \{n : x^n = 1 \},\,$ which, being nonempty and closed under subtraction, comprises a subgroup / ideal of $\:\mathbb Z.\,$ The Euclidean algorithm implies that ideals in $\mathbb Z$ are principal, so every element of a nonzero ideal is a multiple of the least positive element. For an order ideal this simply says that every “possible” order is a multiple of the least possible order $\,\rm m,\ $ i.e. $\rm\; x^n = 1 \,\Rightarrow\, m\mid n.\,$ Compare this ring-theoretic proof to the ubiquitous group-theoretic proof using Lagrange’s theorem.

An *additive* example an order ideal is a **denominator ideal** $\rm\ \{n : n\: x \in \mathbb Z \,\}$ of a fraction $\,x\in\Bbb Q.\,$ Here the above yields: if a proper fraction can be written with a prime denominator then it is the least possible denominator (in the multiplicative sense), i.e. it divides ever other denominator.

Denominator ideals and fractional ideals can yield significant number-theoretical simplifications – in much the same way that fractional arithmetic often serves to simplify integer arithmetic in elementary number theory. For example, see my post on irrationality proofs using the denominator ideal or, more generally, see my proof employing Dedekind’s conductor ideal – a sort of universal denominator for an entire extension ring. Follow the links there for much further discussion.

- Help with Limit: $\lim_{n \to \infty} \frac{(2 n)! e^n (n)^n}{n! (2 n)^{2 n}}$
- Is this a characterization of commutative $C^{*}$-algebras
- Can an odd number $n$ divide $2^n-1$?
- Pullback metric, coordinate vector fields..
- Sum of odd prime and odd semiprime as sum of two odd primes?
- Fibonacci Sequence, Golden Ratio
- Two sets of 3 positive integers with equal sum and product
- Use Picard's Theorem to prove infinite zeros for $\exp(z)+Q(z)$
- The difference between log and ln
- Classification of indecomposable modules over a given ring
- How to calculate this volume?
- On Conjugacy Classes of Alternating Group $A_n$
- Alternative definition of hyperbolic cosine without relying on exponential function
- Representation theory of locally compact groups
- Is the condition “sample paths are continuous” an appropriate part of the “characterization” of the Wiener process?