Intereting Posts

Fourier series for $\phi(x) = x$ on $$
Yoneda implies $\text{Hom}(X,Z)\cong \text{Hom(}Y,Z)\Rightarrow X\cong Y$?
Prove that $A^*A + I$ is invertible
Finding a prime number $p$ and $x, y, z\in \mathbb N$ such that $x^p+y^p=p^z$
Why do certain notations differ around the world?
Sum of random subsequence generated by coin tossing
Are the $\mathcal{C}^k$ functions dense in either $\mathcal{L}^2$ or $\mathcal{L}^1$?
Intuitively, how should I think of Measurable Functions?
Is L'Hopitals rule applicable to complex functions?
Show that $2\tan^{-1}(2) = \pi – \cos^{-1}(\frac{3}{5})$
Priority of the content of a note by Lebesgue from 1905
Calculating equidistant points around an ellipse arc
Height and minimal number of generators of an ideal
Is the $24$ game NP-complete?
Tail bound on the sum of independent (non-identical) geometric random variables

How can I prove that $5^n \equiv 1 (\bmod 2^r$) when $n=2^{r-2}$?

Actually what I am trying to prove is that the cyclic group generated by the residue class of $5 (\bmod 2^r)$ is of order $2^{r-2}$.

- Is there a closed form of the sum $\sum _{n=1}^x\lfloor n \sqrt{2}\rfloor$
- Find the values of $p$ such that $\left( \frac{7}{p} \right )= 1$ (Legendre Symbol)
- How would I determine if there is at least 1 integer that can satisfy 5 congruences all at once?
- How to find the inverse modulo m?
- Calculating the Modular Multiplicative Inverse without all those strange looking symbols
- Proving $11! + 1$ is prime

- Rotation $x \to x+a \pmod 1$ of the circle is Ergodic if and only if $a$ is irrational
- Doubts about a nested exponents modulo n (homework)
- What are the last two digits of $77^{17}$?
- Remainders of Fibonacci numbers
- Prove $(a + b) \mod n = (a \mod n + b \mod n) \mod n$
- Prove that every year has at least one Friday the 13th
- What are the rules for basic algebra when modulo real numbers are involved
- modulo of series summation
- Do inequations exist with congruences?
- Primes for which $x^k \equiv n \pmod{p}$ is solvable

Hint: If $a=1\pmod{2b}$ then $a^2=1\pmod{4b}$.

(Proof: if $a=2bk+1$ then $a^2=4bk(bk+1)+1$. End of the proof.)

Use this for $a=5^n$, $n=2^{r-2}$ and $b=2^{r-1}$, to build a proof by induction on $r$, starting from the $r=2$ case $5^1=1\pmod{4}$.

We divide your original problem into two parts. The specific question you asked has nothing to do with $5$ and is answered for all odd $a$ in Part $1$. The fact that the order of $5$ is actually $2^{r-2}$ and not something smaller is proved in Part $2$.

**Part $1$:** Suppose that $a$ is odd, and $r \ge 3$. Then $a^{2^{r-2}}\equiv 1 \pmod{2^r}$.

Since $2^r$ does not have a primitive root, the order of $a$ modulo $2^r$ is **less** than $\varphi(2^r)$. But the order of $a$ divides $\varphi(2^r)$. Since $\varphi(2^r)=2^{r-1}$, it follows that the order of $a$ is a divisor of $2^{r-1}$ which is *less* than $2^{r-1}$. Thus the order of $a$ divides $2^{r-2}$. It follows that $a^{2^{r-2}}\equiv 1 \pmod{2^r}$.

**Part $2$:** We show that if $r\ge 3$, then $5^{2^{r-3}}\not\equiv 1 \pmod{2^r}$. This will show that the order of $5$ modulo $2^r$ is actually $2^{r-2}$, and not something smaller.

We show by induction that $5^{2^{r-3}}\equiv 1+2^{r-1} \pmod{2^r}$, and so in particular $5^{2^{r-3}}\not\equiv 1 \pmod{2^r}$.

It is easy to check that the result holds at $r=3$. Suppose now that $5^{2^{k-3}}\equiv 1+2^{k-1} \pmod{2^k}$. We show that $5^{2^{k-2}}\equiv 1+2^{k} \pmod{2^{k+1}}$.

By the induction assumption $5^{2^{k-3}}= 1+2^{k-1} +s2^k$ for some $s$. Square both sides, and simplify modulo $2^{k+1}$. We get that

$$5^{2^{k-2}}=(1+2^{k-1} +s2^k)^2 \equiv 1+2^k +2^{2k-2}\pmod{2^{k+1}}.$$

But $2^{2k-2}$ is divisible by $2^{k+1}$, since $k \ge 3$. The result follows.

Hint:

$$

5^{2^{k+1}}-1=(5^{2^k}-1)(5^{2^k}+1)

$$

The latter factor is always congruent to $2\pmod 4$. I recommend that you then prove a result giving the exact power of two that divides $5^{2^n}-1$ by induction on $n$. This gives you the order of the residue class of $5$ modulo any power of two.

Let a be an odd integer=2b+1(say),

$$a^2=4b^2+4b+1=8b(b+1)/2+1=8c+1 $$(say) where $$c=b(b+1)/2$$ an integer (See also If $n$ is an odd natural number, then $8$ divides $n^{2}-1$)

$$a^4=(1+8c)^2=1+16c+64c^2=1+16d $$ for some integer $$d=c+4c^2$$

$$a^8=(1+16d)^2=1+32d+256d^2=1+32e$$

Using induction for n≥3,we get $$a^{2^{n-2}}≡1(mod 2^n).$$

See http://www.amazon.com/Introduction-Theory-Numbers-Ivan-Niven/dp/0471625469

- Prove that in a Noetherian ring, no invertible maximal ideal properly contains a nonzero prime ideal
- How should a numerical solver treat conserved quantities?
- Graph and Number theory
- Question about the radical of the Jacobson radical.
- probability of rolling at least $n$ on $k$ 6-sided dice
- If multiplication is not repeated addition
- Verification of Proof that a nonabelian group G of order pq where p and q are primes has a trivial center
- Is there an intuitive way to see this property of random walks?
- Prove that every prime larger than $3$ gives a remainder of $1$ or $5$ if divided by $6$
- Find a Recurrence Relation
- Hatcher question: How to Cut and Glue from Tetrahedron to Klein Bottle
- Find the real number $x$ represented by continued fraction $$
- Two-dimensional unital complex Banach algebras
- Find the upper bound of the derivative of an analytic function
- Deriving generators for $H^1(T)$: what are $dx$ and $dy$?