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

Modular arithmetic (clock arithmetic) is a system of arithmetic of integers. The basic ingredient is the congruence relation $a \equiv b \bmod n$ which means that $n$ divides $a-b$. In modular arithmetic, one can add, subtract, multiply, and exponentiate but not divide in general. The Euclidean Algorithm, the Chinese Remainder Theorem, and Fermat's Little Theorem are important throughout mathematics. Modular exponentiation plays an important role in cryptography nowadays.

11320 questions
6
votes
8 answers

How to show $(3^ {2n} - 1) \equiv 0 \mod 8$

How can I show that $$3^{2n}-1 \equiv 0 \pmod 8$$ is true? What kind of method should I approach this problem with? I was thinking induction but but chapter isn't about induction so need some help...
6
votes
2 answers

Solve $2^{99}$ mod $101$

My number theory is a bit rusty, so i am trying to recall how to work this problem out. I know that the euler theorem would state that $2^{\phi(101)} \equiv 1$ mod $101$ But in this case, $\phi(101)$ is $100$ so i only know how to calcuate…
6
votes
6 answers

Why is the sum modulo n of elements in $\mathbb{Z}_n^*$ equal to 0?

I'm talking about the set $$\mathbb{Z}_n^* = \{x \in \mathbb{Z}_n : \text{gcd}(x,n)=1\}$$ I noticed that for $n>2$, if you add all the elements in the set, you get $0\mod{n}$. Can someone explain why this is? I also noticed that if $a$ is in the…
quantum
  • 357
  • 4
  • 7
  • 15
6
votes
3 answers

Modular arithmetic and equivalence classes

I completely understand the concept of modulus arithmetic and grasp all the main ideas. The only thing I don’t understand is equivalence classes. The formal definition is: Another interpretation is that modular arithmetic deals with all the…
user26649
6
votes
2 answers

Modularity and prime number sequence

I tried to solve this modular equation involving first $n$ prime numbers. And it is: $$2^{3+5+7+11+13+.....+p_{n-3}+p_{n-2}}\equiv p_{n-1}\ \left(\text{mod }p_{n}\right),$$ where $p_{n}$ is the $n$-th prime number. I couldn't find any solution for…
5
votes
4 answers

Proving $5^n \equiv 1 \pmod {2^r}$ when $n=2^{r-2}$

How can I prove that $5^n \equiv 1 (\bmod 2^r$) when $n=2^{r-2}$? Actually what I am trying to prove is that the cyclic group generated by the residue class of $5 (\bmod 2^r)$ is of order $2^{r-2}$.
5
votes
0 answers

Solving $x^e\equiv a\pmod n$

I am trying to put together the techniques involved in solving $$x^e\equiv a\pmod n, \text{ for known } n\in\mathbb N^*, e\in\mathbb N^*, a\in\mathbb Z_n, \text{ unknown }x\in\mathbb Z_n$$ I'm interested in the slightly different problems…
fgrieu
  • 1,758
5
votes
1 answer

Why does $6^x ≡ 2^{10-x} \pmod{11}$ when $0≤x≤10$?

I was messing around with my calculator earlier today. I graphed the function $6^x \pmod{11}$, and I noticed a pattern, and I "discovered" the following: $$6^x ≡ 2^{10-x} \pmod{11}$$ This works whenever $x$ is an integer between $0$ and $10$,…
PhiNotPi
  • 2,661
  • 3
  • 23
  • 36
5
votes
3 answers

Simplify [(a*b) mod n] mod m

I know that instead of computing (a*b) mod n, I can also compute more efficiently on smaller numbers via [(a mod n)*(b mod n)] mod n. (I need the last mod n, because my result needs to be smaller than n) Is there a way I can easily compute [(a*b)…
torpedo
  • 121
5
votes
2 answers

Doing modular division when denominator and modulus not coprime

So normally if you calculate $n/d \mod m$, you make sure $d$ and $m$ are coprime and then do $n[d]^{-1}\mod m$ , all $\mod m$. But what if $d$ and $m$ are not coprime? What do you do?
5
votes
2 answers

Is it a valid step while solving modular arithmetic equation?

It's probably a very basic question. Is this equation $$91x\equiv21\pmod{56}$$ equivalent to $$35x\equiv21\pmod{56}$$ If so, then what property says that these equations are equivalent?
user1242967
  • 1,727
5
votes
3 answers

exponentiation and modular arithmetic

How would I be able to simplify $$2^x\mod 10^9$$ Since there are only $10^9$ possible values mod $10^9$, somewhere the pattern must repeat. I could have a computer program trudge through it, but I'm dealing with storing potentially 10 billion…
Mike
  • 13,318
5
votes
4 answers

Checking my work for $21^{100}-12^{100}$ modulo $11$

Question 1: Is $21^{100}-12^{100}$ divisible by $11$? My work: Note:$$\begin{align*} & \color{red}{21^{100}}\equiv10^{100}\equiv 100^{50}\equiv1^{50}\equiv1 \mod 11\\ & \color{blue}{12^{100}}\equiv 1^{100}\equiv 1\mod…
Crescendo
  • 4,089
5
votes
1 answer

Algorithm for Hensel's Lifting

If I know the solution for $\;x^2 \equiv n \mod p\;$ (where $p$ is prime and a quadratic residue of $n$), how can I find the solution of $\;x^2 \equiv n \mod p^2$, in an algorithmic way?
5
votes
2 answers

Proofs using linear congruences

We have just covered solving linear congruences, and I am confused about how to use them in proofs. I understand that the linear congruence $$cx \equiv b \pmod m$$ has a unique solution $\bmod m$ if $\gcd(c,m) = 1$, but a general approach to…
Moderat
  • 4,437