khashi70 wrote: $ n$ is a positive integer . prove that : $ 3^\frac {5^{2^{n} - 1}}{2^{n + 2}} \equiv ( - 5)^\frac {3^{2^{n} - 1}}{2^{n + 2}}$ (mod $ 2^{n + 4}$) I think this problem has some errors :

Let \[ a=\frac{5^{2^n}-1}{2^{n+2}},b=\frac{3^{2^n}-1}{2^{n+2}}.\] Then \[ b=\frac{5^{2^n}(1-\frac 85)^{2^n}-1}{2^{n+2}}=a(1-\frac 85)^{2^n}+\frac{(1-\frac 85)^{2^n}-1}{2^{n+2}}.\] Let $ 1-\frac 85=(-5)^c\mod 2^{n+2}$, then $ b=a5^{c*2^n}+\frac{5^{c2^n}-1}{2^{n+2}}\mod 2^{n+2}.$ Therefore $ 3^a(-5)^{-b}=1\mod 2^{n+4}$ if and only if $ a-b+ca=0\mod 2^{n+2}$, if and only if $ ac=\frac{5^{c2^n}-1}{2^{n+2}}\mod 2^{n+2}$. Because $ 5^{c2^n}=(1+a*2^{n+2})^c=1+ac*2^{n+2}+\frac{c(c-1)}{2}a^2*2^{2n+4}+O(2^{3n+6})$, it is true.

it is easy problem. it is cleary to prove $ 2^{n+2}||5^{2^n}-1$. it is true for $ n=1$. so let it is true for $ n-1$ so prove for $ n$. $ 3^{\frac {5^{2^n-1}}{2^{n+2}}}-(-5)^{\frac {5^{2^n-1}}{2^{n+2}}}= (3^{\frac {5^{2^{n-1}-1}}{2^{n+1}}}-(-5)^{\frac {5^{2^{n-1}-1}}{2^{n+1}}})(q)$. where $ q=a^{k-1}+a^{k-2}b+\ldots +b^{k-1},a=3^{\frac {5^{2^{n-1}-1}}{2^{n+1}}},b=(-5)^{\frac {5^{2^{n-1}-1}}{2^{n+1}}},k=\frac {5^{2^{n-1}+1}}{2}$. so $ 2|q$ and $ 3^{\frac {5^{2^{n-1}-1}}{2^{n+1}}}-(-5)^{\frac {5^{2^{n-1}-1}}{2^{n+1}}} \equiv 0 (2^{n+3})$(problem for $ n-1$) so $ 3^{\frac {5^{2^n-1}}{2^{n+2}}}-(-5)^{\frac {5^{2^n-1}}{2^{n+2}}} \equiv 0 (2^{n+4})$

your problem is not same.

Rust wrote: Let $ 1 - \frac 85 = ( - 5)^c\mod 2^{n + 2}$, then $ b = a5^{c*2^n} + \frac {5^{c2^n} - 1}{2^{n + 2}}\mod 2^{n + 2}.$ could you please explain this statement and how can you say that a fraction has residue, thanks in forward [/quote]

Matematika wrote: Rust wrote: Let $ 1 - \frac 85 = ( - 5)^c\mod 2^{n + 2}$, then $ b = a5^{c*2^n} + \frac {5^{c2^n} - 1}{2^{n + 2}}\mod 2^{n + 2}.$ could you please explain this statement and how can you say that a fraction has residue, thanks in forward [/quote] http://mathworld.wolfram.com/Congruence.html

Uhm, first we introduce the well-known lemma: if 2 divided n then $ v_{_2}{(a^n-1)}$=$ v_{_2}{(a^2-1)}+v_{_2}{\frac{n}{2}}$ if 2 didn't divide n then $ v_{_2}{(a^n-1)}$=$ v_{_2}{(a-1)}$ by above lemma exists a such that $ -3 \equiv 5^a (mod 2^{n+4})$ so $ (-3)^\frac{5^{2^{n}}-1}{2^{n+2}}\equiv (5)^\frac{3^{2^{n}}-1}{2^{n+2}}$ (mod $ 2^{n+4}$) if only if $ \frac{5^{2^{n}}-1}{2^{n+2}}$ . a $ \equiv$ $ \frac{3^{2^{n}}-1}{2^{n+2}}$ (mod $ 2^{n+2}$) if only if ($ {5^{2^{n}}-1}$ ). a $ \equiv$ $ {3^{2^{n}}-1}$ (mod $ 2^{2n+4}$) by above lemma again we have because $ -3 \equiv 5^a$ (mod $ 2^{n+4}$) then $ {3^{2^{n}}-1}$ $ \equiv$ $ 5^{a.2^n} -1$ (mod $ 2^{2n+4}$) and of course $ 5^{a.2^n} -1 - (a.5^{2^n} -1)$ is divisible by $ {({5^{2^n} -1})}^2$ which is divisible by $ 2^{2n+4}$

It's a direct application of the following lemma: Lemma: if $a\equiv 3$ or $5$ $(\mod 8)$ then for $k\ge 4$ the set $\{ \pm a^i|0\le i< 2^{k-2} \}$ is a complete residue system modulo $2^k$.

inio wrote: Uhm, first we introduce the well-known lemma: if 2 divided n then $ v_{_2}{(a^n-1)}$=$ v_{_2}{(a^2-1)}+v_{_2}{\frac{n}{2}}$ if 2 didn't divide n then $ v_{_2}{(a^n-1)}$=$ v_{_2}{(a-1)}$ by above lemma exists a such that $ -3 \equiv 5^a (mod 2^{n+4})$ Could you please explain this point. Why from that lemma we can know that exists $a$ such that $-3 \equiv 5^a \pmod{2^{n+4}}$.

Anyone ?? Please help me!

shinichiman wrote: Anyone ?? Please help me! I think it's just induction on $n$. And also use some binomial expansion

Note that $\nu_2(5^{2^n}-1)=n+2$ and $\nu_2(3^{2^n}-1)=n+2$, so both exponents of LHS and RHS are odd positive integers. Now, since $\mathrm{ord}_{2^{n+4}}(5)$ must be some power of two, let it be $2^{\ell}$. We have $2^{n+4}\mid 5^{2^{\ell}}-1\implies \ell \geqslant n+2$. This means $\ell =n+2$. Then, consider $2^{n+2}$ residues modulo $2^{n+4}$ of the numbers $5^i$ where $i$ be non-negative integer smaller than $2^{n+2}$. These $2^{n+2}$ residues must be pairwise distinct, and also $\equiv 1\pmod{4}$. Note that there're exactly $2^{n+2}$ possible such residues of modulo $2^{n+4}$. So, since $-3\equiv 1\pmod{4}$, there exists positive integer $t$ that $5^t\equiv -3\pmod{2^{n+4}}$. The problem is equivalent to showing that $(-3)^{\frac{5^{2^n}-1}{2^{n+2}}}\equiv 5^{\frac{3^{2^n}-1}{2^{n+2}}} \pmod{2^{n+4}}$. Note that it is then equivalent to $5^{t\times \frac{5^{2^n}-1}{2^{n+2}}}\equiv 5^{\frac{3^{2^n}-1}{2^{n+2}}} \pmod{2^{n+4}}$. Since $\mathrm{ord}_{2^{n+4}}(5)=2^{n+2}$, we need to show that $t(5^{2^n}-1)\equiv 3^{2^n}-1\pmod{2^{n+2}\times 2^{n+2}}$. Since $\nu_2(5^{2^n}-1)=n+2$, we've $1+t(5^{2^n}-1)\equiv \left( 1+(5^{2^n}-1)\right)^t\pmod{(2^{n+2})^2}$. Hence, $1+t(5^{2^n}-1)\equiv (5^{2^n})^t=(5^t)^{2^n} \pmod{2^{2n+4}}$. The rest is to show that $(5^t)^{2^n}\equiv 3^{2^n}\pmod{2^{2n+4}}$. Note that $2^{n+4}\mid 5^t-(-3)\implies \nu_2((5^t)^{2^n}-(-3)^{2^n})=\nu_2(5^t-(-3))+\nu_2(2^n)\geqslant 2n+4$. This gives $(5^t)^{2^n}\equiv 3^{2^n}\pmod{2^{2n+4}}$ as desired, done.

ThE-dArK-lOrD wrote: we've $1+t(5^{2^n}-1)\equiv \Big( 1+(5^{2^n}-1)\Big)^t\pmod{(2^{n+2})^2}$ Why do we have it??

@above Use binomial theorem.

inio wrote: $ 5^{a.2^n} -1 - (a.5^{2^n} -1)$ is divisible by $ {({5^{2^n} -1})}^2$ which is divisible by $ 2^{2n+4}$ Can someone please tell why is $$ 5^{a \cdot 2^n} - a \cdot 5^{2^n} $$divisible by $ \left(5^{2^n} - 1 \right)^2$ ?