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
4
votes
1 answer

What additional information is needed to know the answer? (Modular Arithmetic)

I have 2 numbers $n_1 = 1\pmod6$ and $n_5 = 5 \pmod 6$ I wish to know $\frac{4n_1-1}{3} \pmod 6$ and $\frac{2n_5-1}{3} \pmod 6$. Since the answer varies depending on $n_1$ and $n_5$ I was wondering if there is some additional knowledge I might have…
Ben Crossley
  • 2,544
4
votes
5 answers

Can modulus be negative?

For example, if I compute $18 \bmod 5$, the result will be $3$. This will be because of $5\cdot3+3=18$, but can I have $5\cdot4-2=18$ which gives me $-2$?
drum
  • 625
4
votes
4 answers

Find $6^{273} + 8^{273}\pmod{49}$

The number $6^{273} + 8^{273}$ divided by $49$ has a remainder, what is its value? I used the totient function to compute for modulo 49. $6^{42}$ and $8^{42}$ are $-1$ and $1$ mod $49$ respectively, $273/49$ is equal to $5$ with a remainder of…
SuperMage1
  • 2,486
4
votes
5 answers

How do I subtract times?

I have an embarrassingly basic modular arithmetic question. I understand that I can subtract, for example, 1 hour from 10 o'clock to get 9 o'clock, or even 2 hours from 1 o'clock to get 11 o'clock; but how do I subtract 2 o'clock from 11 o'clock to…
orome
  • 2,361
4
votes
1 answer

Is there a way to make (x mod p) mod q = x mod q possible?

Is it possible to restrict $p$ and $q$ ($p, q \in primes$) in such a way that $(x$ mod $p)$ mod $q \equiv x$ mod $q$ always holds? I actually need a looser condition: I need that if $x \equiv 0$ mod $q$, then $x \equiv 0$ mod $p$ mod $q$. Is the…
AdveRSAry
  • 165
  • 6
4
votes
1 answer

Does $a = 0$ iff $a \equiv 0 \ (\operatorname{mod} p)$ for every prime $p$?

Suppose $a \in \mathbb{Z}$. Does $a = 0$ iff $a \equiv 0 \ (\operatorname{mod} p)$ for every prime $p$? It's probably a silly question, but I don't know how to go about it. I'm motivated by the common contest math trick of considering a…
4
votes
2 answers

Explanation of Digital Root/ Sum formula

The formula to find the digital root/ sum is: digital root of n = 1 + ( (n - 1) % 9 ) Can someone explain me the intuition behind this formula? Why does this result give the sum of digits?
4
votes
4 answers

Find all $n$ with $\!\bmod n\!:\, a\,$ invertible $\Rightarrow a^{-1} \equiv a,\,$ i.e. $a^2\equiv 1$

Find all positive integers $n$ such that $a \equiv a^{-1} \pmod{n}$ for all invertible $a$ modulo $n$. I found that $n = 1,2,4,6,8,12,24$ satisfy this. How can we prove that these are all of them?
Puzzled417
  • 6,956
4
votes
1 answer

modular logs (index arithmetic) to find remainder

use the index arithmetic to find the remainder when $46^{88}$ times $5^{400}$ is divided by $29$. I have solved this using typical modulo operations first by reducing $46$ to $17$ then finding the order of $17$ and dividing $88$ by the order. which…
4
votes
2 answers

Value of $\sum_{i=1}^{p} i^k \pmod{p}$

I found a statement that $$\sum \limits_{i=1}^{p} i^k \equiv \begin{cases} -1 && (p-1) \mid k \\ 0 && \text{otherwise}\end{cases} \pmod{p}$$ for a prime $p$ and positive integer $k$. The result is obvious when $k$ is odd or equals $p-1$ but I can't…
Karolis Juodelė
  • 9,702
  • 1
  • 25
  • 39
4
votes
2 answers

What's the answer of (10+13) ≡?

As to Modulus operation I only have seen this form: (x + y) mod z ≡ K So I can't understand the question, by the way the answers are : a) 8 (mod 12) b) 9 (mod 12) c) 10 (mod 12) d) 11 (mod 12) e) None of the above
mko
  • 203
4
votes
2 answers

Why $\,p\, (p^{-1}\!\bmod q) + q\,(q^{-1}\!\bmod p) = pq + 1?$

This is going to sound like a stupid question, but I cannot understand how I get this result (I understand why, but it looks like there is no relation). For $p, q$ primes why do we have this? $$p\, (p^{-1}\!\bmod q) + q\,(q^{-1}\!\bmod p) = pq +…
4
votes
4 answers

Solve the simultaneous congruences: $2n + 6m\equiv 2 \pmod{10}$ and $n + m\equiv -2 \pmod{10}$

To solve the simultaneous congruences $$2n + 6m\equiv 2 \pmod{10}$$ and $$n + m\equiv -2 \pmod{10}$$ I tried to add the two congruences together so I got: $$3n + 7m\equiv 0 \pmod{10}$$ But I am not sure if that's right and if it is, what to do next…
4
votes
3 answers

How can a = x (mod m) have multiple meanings in modular arithmetic?

It seems to me that a = x (mod m) can mean either that a is the remainder of x divided by m or that the remainders of a and x are the same when divided by m (eg. with respect to mod m). For example: 2 = 6 (mod 4) would be the first meaning I…
dhatch387
  • 155
4
votes
3 answers

How do you find a multiplicative inverse in modulo arithmetic?

In one of my lectures I have been given this example: When Googling 'multiplicative inverse' most of the tutorials seem to indicate it's as easy as just multiplying a number by the number divided by 1. What's different in this example? How do you…
WewLad
  • 189