# Questions tagged [modular-arithmetic]

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 $a-b$.

12,189 questions
Filter by
Sorted by
Tagged with
1 vote
47 views

### Homomorphism between $\mathbb{Z}/m$ and $\mathbb{Z}/n$

The lecture notes I am working through assert, but leave as an exercise, that if $n\mid m$, then the map $f:\mathbb{Z}/m\to \mathbb{Z}/n$ sending$$x\mapsto x\pmod n$$is a surjective homomorphism. My ...
• 219
1 vote
34 views

• 171
34 views

### How to handle modulus when there is division operation in the expression? [duplicate]

I am asked to print all numbers modulus of $1000000007$. My expression is $x*(1+f(x))/2$ For cases when x is even it is simple as i can do (x/2) first, then do: $((x/2)*(1+f'(x)) modulus 1000000007$...
53 views

• 6,047
155 views

• 73
1 vote
69 views

### How to calculate (20! * 12!) mod 2012 fast? [closed]

$(20! \cdot 12!) \mod 2012$ I calculated the answer multiplying each ${1 \cdot 2 \cdot 3\ldots n}$ with $\mod k$ one-by-one and found that the solution is $1684$. But I wonder if there is a faster ...
• 173
53 views

### If $u$ is a unit in $\mathbb{Z}_p$ for prime $p$, then $u^{p-1}=[1]$. Why? [closed]

As part of a proof of Fermat's little theorem, my teacher used that if $u$ is a unit in $\mathbb{Z}_p$ with $p=$ prime then $u^{p-1}=[1]$. Can someone help me understand why that statement is true?
• 67
1 vote
23 views

### proof that $(b^n-1)/(b-1)$ is not prime if n is a pseudoprime not prime of the base $b$.

The question of my exercise says: Proof that, if $n$ is a pseudoprime not prime of the base $b$ (i.e. $b^{n-1}\equiv 1 (\mod n)$) then $N=(b^n-1)/(b-1)$ is also a pseudoprime not prime. I have proven ...
• 33
51 views

### Can I write a congruence like this?

I wrote down the following $\omega_e(P) \equiv 0,n\pmod{\! k}$, where $n|k$. What I'm trying to say is that $\omega_e(P)$ is either congruent to $0$ mod $k$ or $n$ mod $k$. Is this the correct way to ...
39 views

• 658
### Prove that $\sum_{i = 1}^{N} 1+ (2i \bmod N) = N(N + 1) / 2$ for odd N.
I was able check by hand that for odd $N$ the $1+ (2i \bmod N)$ produces all values between $1$ and $N$ and for even $N$ there are repeats. But I've no ideas on how to write a mathematical proof for ...