Remainder of a power tower under modulo $2013$

I have an expression like this: $$\left(\large 6000^{5999^{5998^{5997^{{\ldots^{1}}}}}}\right)\bmod 2013$$ Then which method should I use to solve it? Please provide the method not the answer. Editor’s Note: Note that this is a power tower with different values and not the same value as with general tetration. Also, don’t confuse tetration with exponentiation. Both are completely … Read more

If x^2\equiv a\pmod nx^2\equiv a\pmod n, then (n-x)^2\equiv a\pmod n(n-x)^2\equiv a\pmod n

Given that x is a solution to x^{2}\equiv a \pmod n, show that y=n-x is also a solution. Please don’t solve, just give me a hint. Answer Hint Expand y^2 = (n – x)^2 modulo n. (This is perhaps easier to see intuitively if we recall that n – x \equiv -x \bmod n, in … Read more

Prove that x^2 \equiv y^2 \pmod px^2 \equiv y^2 \pmod p if and only if x \equiv y \pmod px \equiv y \pmod p or x \equiv -y \pmod px \equiv -y \pmod p. Hint: x^2-y^2 = (x+y)(x-y)x^2-y^2 = (x+y)(x-y).

This is the exercise verbatim: An integer n is a square modulo p if there exists another integer x such that n \equiv x^2 \pmod p. Prove that x^2 \equiv y^2 \pmod p if and only if x \equiv y \pmod p or x \equiv -y \pmod p. Hint: x^2-y^2 = (x+y)(x-y). This is my … Read more

Congruence of 2 fractions—how to properly rewrite in terms without modulo?

EDIT: Following Theo’s comment, the equivalence holds since one can (must) rewrite $1/a$ as $(1+23k)/a$. Provided that $$\frac{1}{25} \equiv \frac{1}{2}\pmod {23}$$ is true, why can I not rewrite it like usually possible? $$\frac{1}{25}=\frac{1}{2}+23k ~\text{ for }~k \in \mathbb Z$$ $$\implies 2=25+50\cdot23k, \text{which is impossible.}$$ I guess that the factor 50 somehow may be ignored here, … Read more

Problem in proof of Chinese remainder theorem, and applying it.

Please don’t mark it as duplicate. First read the whole question. So Chinese Remainder Theorem states that,: Let $n_1,n_2,…,n_k$ be $k$ positive integers which are pairwise relatively prime. If $a_1,a_2,…,a_k$ are such that $(a_j,n_j)=1$ for $j=1,2,…k$ then the congruences $$a_1x \equiv b_1(\mod n_1),a_2x \equiv b_2(\mod n_2),…,a_kx \equiv b_k(\mod n_k)$$ have a common solution which is … Read more

When can Z/pZ\mathbb{Z}/p\mathbb{Z} be recovered by [0][0] and [kn][k ^n]?

One can see that Z/19Z={[0],[1],…,[18]}={[0],[31],[32],…,[318]}. If I have Z/pZ, p>2 prime, when is there a k∈{2,3,…,p−1} such that [kn] and [0] recover Z/pZ? Further, when is there a prime k? I’m a little removed from my last algebra course, but this interested me and I couldn’t come up with a solution offhand. Edit: nonessential to … Read more

Order of a prime power modulo a prime power

Suppose that q=pn where p is a prime. Now assume that q≡1 (mod l), where l is a different prime, and that q≢1 (mod l^2). How would I find the multiplicative order of q (mod l^k) for arbitrary k? So far I have deduced (maybe wrongly) that the order of q in (\mathbb{Z}/l^2\mathbb{Z})^{\times} is l … Read more

Are there infinite numbers $\not\equiv 2 \pmod {n}$, where n is any prime?

It’s been proven there are infinitely many primes. This means that there exist infinitely many $m$ such that for all other prime $n$, “$m \not\equiv 0 \pmod{n}$”. My question is then, would this imply there exist infinitely many $m$ such that for all prime $n$ other than $n=m-2$, “$m \not\equiv 2 \pmod{n}$”? How about $4 … Read more