# Tag Info

1 vote
Accepted

### Prove that any automorphism $\phi \in Aut(\mathbb{Z}_n)$ is determined by $\phi([1])$ and that $\phi([1])$ must be a generator for $\mathbb{Z}_n$

Since every $k\in\Bbb Z_n$ is $1^k$ (multiplicative notation), a homomorphism of a cyclic group is completely determined by what it does to any generator. And the homomorphism $\phi$ is bijective ...
• 583

### Prove that any automorphism $\phi \in Aut(\mathbb{Z}_n)$ is determined by $\phi([1])$ and that $\phi([1])$ must be a generator for $\mathbb{Z}_n$

You just need to prove that $o(\phi(1)) =n$. Which is trivial since $$\phi(1)^n=\phi(1^n) =\phi(n) =\phi(0) =0$$
• 3,787

### Prove for any $[a] \in \mathbb{Z}^\times_n$ multiplication by $[a]$ defines an automorphism $\alpha_{[a]}: \mathbb{Z}_n \to \mathbb{Z}_n$

I would suggest that you don't bother with the specific case of $\mathbb Z_n$. Just prove that for any ring $(R, + , \cdot)$ and $a \in R$ the map $$\varphi_a: x \mapsto ax$$ is a homomorphism of the ...
1 vote
Accepted

### Prove for any $[a] \in \mathbb{Z}^\times_n$ multiplication by $[a]$ defines an automorphism $\alpha_{[a]}: \mathbb{Z}_n \to \mathbb{Z}_n$

Fix $[a]\in\Bbb Z_n^\times$. You need to show the homomorphism property $$\alpha_{[a]}([k]+[l])=\alpha_{[a]}([k])+\alpha_{[a]}([l])$$ for all $[k],[l]\in\Bbb Z_n$, together with either surjectivity or ...
• 38.7k

### How to find the last two digits of $2011^{2011}$

SOLUTION $1$ : $2011\equiv 11 \mod (100)$ $2011^2\equiv 11^2 \equiv 21 \mod (100)$ $2011^3\equiv 11^3 \equiv 31 \mod (100)$ $2011^4\equiv 11^4 \equiv 41 \mod (100)$ ...................................
• 4,795

### Is it possible to generalize this equation more?

This is very nice. It relies to the Tarry-Escott problem, on which there is a vast literature going back more than 100 years. I do not know how much you know of this. I suggest you consult Dickson, ...

### Let $n$ be a positive integer. Show that $n\phi(n)=\phi(n^2).$

Since everything that could have been said, has already been said, let me add those probabilistic intuitions involving $\varphi$ function (because I like them)- Note that if $a$ is coprime to $n^2$, ...
• 5,746
Accepted

### Luhn algorithm for odd and even card numbers?

For odd placed digits going back from the check digit, you have the following mapping: 0 2 4 6 8 1 3 5 7 9 Then add all digits, including the check digit it should form a multiple of ten So the ...

### Proof for a prime-generating sequence

$$n+2=6k+1$$ by Wilson's theorem $$(n+1)!\equiv -1\pmod {n+2}$$ it follows that $$n!\equiv 1\pmod{n+2}$$ and that $$(n-1)!\equiv -(2^{-1})\equiv 3k\pmod {n+2}$$ and $$-n\equiv 2\pmod {n+2}$$ so ...
Accepted

### Given $245^2\equiv 1\pmod{2501}$. Find $x,y$ such that $x\cdot y=2501$.

Note that the factorization of $a^2-1$ is $(a-1)(a+1)$. So, \begin{align*}245^2-1^2 &\equiv 0 \mod 2501 \\ (245-1)(245+1) & \equiv 0 \mod 2501 \\ 244\cdot 246 &\equiv 0 \mod 2501.\end{...
• 152
Accepted

### Solutions to the equation $x^y \equiv y^x$ in $\mathbb Z / p \mathbb Z$, $p$ prime.

This is more complicated than it looks because solutions to $x^y\equiv y^x\bmod p$ (with $p$ prime) are actually not defined $\bmod p$. They are defined $\bmod p(p-1)$ because the power varies with ...
• 29.8k
1 vote
Accepted

• 236

### Can we generalize the quadratic formula to modular arithmetic?

Yes, though it's not well-known (and despite incorrect claims to the contrary in other answers here) it is true that the quadratic formula (completing the square) can be used to solve modular ...
• 258k

### How to find $40! \mod 5^{10}$?

Because $5^9$ divides $40!$, we can use $ka \bmod kb =k(a \bmod b)\,$ [mod distributive law] to get $40! \bmod 5^{10} = 5^9\cdot(\frac{40!}{5^9} \bmod 5)$. Hence we really only need to find the ...

### Can we generalize the quadratic formula to modular arithmetic?

Consider a concrete example: $x^2-5x+6=0\ (\operatorname{mod} 1000)$ A brute-force search gives the integer solution set $x \in \lbrace 2, 3, 378, 627 \rbrace\ (\operatorname{mod} 1000)$. The ...
• 8,553

### Missing a detail about Chinese Remainder Theorem and $Z$ Ring isomorphisms.

Firstly observe that the kernel of the map defined from $\mathbb{Z}$ is $m\mathbb{Z}\cap n\mathbb{Z}$ which is equal to $mn\mathbb{Z}$ only when $m,n$ are coprime.\ Secondly try to show that the map ...
### How do you find out the number of solutions to $x^a \equiv b \pmod{n}$, $x^{12} \equiv 1 \pmod{27}$?
There is a general procedure to these type of problems. Observation. Suppose $(\mathbb{Z}/m\mathbb{Z})^\times=\langle g\rangle$ is cyclic and $\gcd(a,m)=1$. We want to find the solution to the ...
First you find $\frac{1}{271} = .\overline{00369} = \frac{369}{99999} = \frac{41}{11111}$ The rest is "simple" arithmetic.