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
2
votes
3 answers

Help with the proof for modulo multiplication

My lecturer's powerpoint has the following proof but I feel like it's missing a step. Could I get some help with how the final conclusion is reached. Thank you. For multiplication, since we know that $m|(b-a)$ we also know $m|(b-a)c$, that is, $ac…
2
votes
4 answers

Modular arithmetics

I've been reading about some examples concerning DSS/DSA signature security and there is one part of an example that I do not understand the maths. Namely, how do you calculate this: $w = (s^{-1}$ $mod$ $q)$ In this example let's say $q = 13$ and…
mzm
  • 65
  • 4
2
votes
3 answers

Determine the smallest integer $k$ such that $4^k \equiv 1 \pmod{19}$.

The following is a question I've come across, which states: Determine the smallest integer $k$ such that $4^k \equiv 1 \pmod{19}$. We know that, according to Fermat's Little Theorem, $a^{p-1}\equiv 1 \pmod{p}$, and because $19$ is prime, it must be…
Cisplatin
  • 4,675
  • 7
  • 33
  • 58
2
votes
1 answer

Having A Problem With Chinese Remainder Theorem

Find all solutions, if any, to the system of congruences $$\begin{align} x&\equiv 7 \pmod{9}\\ x&\equiv 4 \pmod{12}\\ x&\equiv 16 \pmod{21} \end{align}$$ Solution: Using the Chinese Remainder theorem, we get that this system is equivalent to the 5…
Cloules
  • 21
  • 2
2
votes
3 answers

How to calculate the mod value of a rational/irrational value?

We have a course in network security this semester and we are being taught RSA algorithm. I came across a typical math problem that I was unable to solve here. $$D*E \equiv 1 \mod{\phi(n)}$$ This became $$D \equiv E^{-1} \mod{\phi(n)}$$ How do you…
2
votes
1 answer

number theory modular arithmrtic system with primes.

For how many distinct primes pqr can we have $$pq \equiv 1 \bmod r$$ $$pr \equiv 1 \bmod q$$ $$rq \equiv 1 \bmod p$$??? I've never arrived at something like this before ( i got here wile doing an olympiad problem)
Asinomás
  • 105,651
2
votes
3 answers

Divisibility problem with modular arithmatic

Here's the question: "When an integer $n$ is divided by 6, the remainder is 5. What are the possible values of the remainder when $9n$ is divided by 8?" I'm not entirely sure how to decipher this questions because I'm having a hard time…
Dimitri
  • 1,287
2
votes
2 answers

Fermat's Little Theorem and Prime Moduli

I am given two distinct primes $p$ and $q$, where $$m = p*q$$ Also, $$ \begin{cases} r\equiv 1\mod p-1\\ r\equiv 1\mod q-1 \end{cases} $$ I have to show that given an integer a, show that $$a^r \equiv a \mod (m)$$ I'm not sure how to get started. I…
2
votes
3 answers

Why is zero mod zero undefined?

(Edit: This is not a duplicate of the question about n % 0. I'm specifically asking about 0 % 0.) Why is zero mod zero undefined? To me, the answer must be zero, because $0 \times N + M = 0$ has only one solution for $M$, zero. (Assuming $M$ and $N$…
user541686
  • 13,772
2
votes
1 answer

How to solve the equation $x^2=a\bmod p^2$

What is the standard approach to solve $x^2=a\bmod p^2$ or more general $x^n = a\bmod p^n$ ?
Ibrahim
  • 225
2
votes
1 answer

Solving modular equations of two variables

$$7x + 9y \equiv 0 \pmod {31}$$ $$2x - 5y \equiv 2 \pmod {31}$$ I'm supposed to find the x, but I'm stuck in the middle. First I tried to get rid of y. $$53x \equiv 18 \pmod {31}$$ Here now I don't know what to do with this. Can anyone help me…
More Code
  • 221
2
votes
1 answer

Prime trios of the form $p$,$p+2$,$p+4$

My question is about number theory about the prime numbers. Here is the question: Prove that there is only one prime trio of the form $p$,$p+2$,$p+4$. I mean,we can only find the primes 3,5,7 That satisfies the condition.
juliet
  • 349
2
votes
2 answers

Modular exponentiation problem

$10^7 \pmod {77}$ I tried repeated squaring, which worked but took many computations. I also tried Fermat's little theorem, but since $7 < 77$ I didn't know how to use it. Any simpler way to do this?
2
votes
4 answers

How to show that $10^n - 1$ is divisible by $9$

How can I show that $10^n-1, 10^{n-1}-1,...., 10-1$ are all divisible by 9? I was considering using Euclid's algorithm, but I can't find a way to get that to work.
user82004
2
votes
2 answers

Linear equations congruence

I'm having some trouble with the following: Find integers x and y in the set $\{0, 1, 2, 3, 4\}$ such that $$ 2x - 4y \equiv 1 \pmod 5 $$ $$ 3x + y \equiv 2 \pmod 5 $$ Well I'm a little confused on how to solve for a system of linear congruence. I…
Dimitri
  • 1,287