# Tagged Questions

Modular arithmetic (clock arithmetic) is a system of integer arithmetic based on the congruence relation $a \equiv b \pmod{n}$ which means that $n$ divides $b-a$.

33 views

### Show that Z*n is the maximal subset of Zn which is a group with the operation [a] · [b] = [ab].

Let Zn be the set of equivalence class of integers mod(n) which are relatively prime to n, i.e. Zn = 􏰀[i] | gcd(n, i) = 1􏰁. So I understand how this works when the binary operation is ...
16 views

### If $a\equiv b \pmod{p_i}$ for $i=1,2,…,k$ then prove $a\equiv b \pmod{p_1p_2\cdots p_k}$

If $a\equiv b \pmod{p_i}$ for $i=1,2,\cdots,k$ then prove $a\equiv b \pmod{ p_1p_2\cdots p_k}$ $a\equiv b \pmod{p_1}$ implies $a-b=p_1x_1$ Similarly, $a-b=p_2x_2,\ \cdots,\ a-b=p_kx_k$ So, ...
23 views

### Using Modulo reduction

I'm really confused on how to do modular reduction. I understand we're supposed to take the factor of the exponent? for example how would I go about doing modular reduction on: $5^{17}$ mod 16
35 views

### I don't understand a step in the proof of Euler's Theorem, please explain

I am trying to learn the proof for Euler's theorem which states: If $\gcd(a,m)=1$ then $a^{\phi(m)} \equiv 1 \mod m$. The proof goes like this. Take the reduced residue system modulo $m$. ...
19 views

### Showing Modulo Congruence Amongst Prime Divisors (Number Theory)

I'm having trouble figuring out how to show the general existence part of the following problem. Suppose $n\in\{1,2,3...\}$ and $n\equiv 7\mod{10}$. Show that $\exists$ a prime divisor $p$ of $n$ ...
11 views

### Name of that extension of modular inverse?

The modular inverse is a well-defined involution over $\mathbb Z_n^*$: when $\gcd(x,n)=1$, the inverse of $x$ modulo $n$, noted $x^{-1}\bmod n$, is the single integer $z$ with $x\cdot z\equiv1\pmod n$ ...
24 views

### What to do if the modulus is not coprime in the Chinese remainder theorem?

Chinese remainder theorem dictates that there is a unique solution if the congruence have coprime modulus. However, what if they are not coprime, and you can't simplify further? E.g. If I have to ...
94 views

### Remainder when ${45^{17}}^{17}$ is divided by 204

Find the remainder when ${45^{17^{17}}}$ is divided by 204 I tried using congruence modulo. But I am not able to express it in the form of $a\equiv b\pmod{204}$. $204=2^2\cdot 3\cdot 17$
18 views

### What are the values of b such that the matrix [(1,1)(b,1)] is invertible mod 26.

What are the values of b such that the matrix [(1,1)(b,1)] is invertible mod 26. I figured that the matrix is only invertible if its determinant and the n value 26 's gcd is 1, meaning they are ...
32 views

### Find a solution $x\in\mathbb{Z_{\mathrm{784}}}$ for $x\cdot\overline{602}=\overline{308}$

I know that I have to find a positive integer $x$ that I can multiply with $602$ and then divide the result by $784$ so that the remainder of that integer division is $308$. I am sure that this is ...
39 views

### Solve the following congruence: $x(x+1)(x+2) \equiv 0 \pmod{221}$

Find the first five solutions for, $$x(x+1)(x+2) \equiv 0 \pmod{221}$$ I am very confused. By CRT, $x(x+1)(x+2) \equiv 0 \pmod{13}$ and $x(x+1)(x+2) \equiv 0 \pmod{17}$ But these two ...
82 views

### Last digit of $235!^{69}$

Problem What is the last digit of $235!^{69}$? It's been far too long since I did any modulo calcuations, and even then, the factorial would set me back. My initial thought goes to the last digit ...
56 views

### How can I prove that $\frac{21n -3}{4}$ and $\frac{15n+2}{4}$ are never both integers?

I have converted this to a problem of modular arithmetic. I seek to prove that $21n-3$ and $15n+2$ are never congruent to $0\pmod 4$ for the same value of $n$. I observed that $21n$ is ...
68 views

### Show that the equation $x^2+y^2+z^2= (x-y)(y-z)(z-x)$ has infinitely many solutions in integers $x, y, z$.

Show that the equation $x^2+y^2+z^2= (x-y)(y-z)(z-x)$ has in finitely many solutions in integers $x, y, z$. It seems like if I find a set of $x,y,z$ that satisfy this for any values that will ...
8 views