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

Assume $p \equiv 3 \pmod{4}$, and there exists $x$ such that $n \equiv x^2 \pmod{p}$, find one possible value of $x$ given $n$ , $p$

From Assume $p \equiv3 \pmod 4$ and $n \equiv x^2\pmod p $. Given $n$ and > $p$, find one possible value of $x$., it appears that one possible value of x that fulfills Euler's criterion with the constraint for $p$ specified in the title is $x \equiv…
leontp587
  • 149
0
votes
1 answer

Figuring out a high power modulo

Could you walk me through the most efficient way to solve this modulo? $276^{247} \mod 323$
0
votes
2 answers

What is the correct way to find the largest multiple less than Z?

I have a sum series of large numbers (of the order of $10^{15}$) as Z. I need to find out the larges multiple of 1999 that is less than or equal to Z. Formally, $$Z = \sum_{i}^na_i$$ where $a_i >= 10^{15}$. I need to find $Y$ such that $1999 *Y <=…
user3243499
  • 369
  • 5
  • 16
0
votes
1 answer

How to calculate $276^{246} \mod 323$ without a calculator?

How do I simplify this expression? $276^{246} \mod 323$ Thank you so much.
0
votes
2 answers

Modulus of the same number with different prime bases

My question is how to show solve problems as such: $$x \ mod \ 3= 0$$ $$x \ mod \ 5= 2$$ $$x \ mod \ 15 = ?$$ By trial and error I found that x can be 27, and hence answer is 12. But how can I solve similar questions without trial and error?
errorist
  • 315
0
votes
1 answer

Numbers to form arithmetic progression

Find the condition for 3 given numbers x1, x2 and x3 to be terms of an arithmetic progression (obviously the same). Well, I don't know what exactly the problem is asking: Assuming, wlg that x3>x2>x1: It must be x2-x1= mr (where m is an integer and r…
0
votes
1 answer

Modular Linear Congruences Puzzle

I'm learning about solving systems of modular linear congruences in my discrete mathematics class. Recently, my teacher posed a puzzle that I can't seem to solve: These eight small-number triples are not random: [[1 1 3] [1 1 4] [1 4 3] [1 4 4] [2…
0
votes
0 answers

Solving modulo equations

What is the simplest way to find all possible solutions for $x^e~ \equiv~ 0 ~~(mod~ n)$? What should be the range of the value of $x$?
chelsea
  • 195
0
votes
1 answer

Computing mod with fractions

I know that $12(7)^{-(1)}=31(mod 41)$, but I have no idea why. $12(7)^{-(1)}=12/7 \approx 1.714285714$. This is an isolated part of an example of the Pohlig-Hellman algorithm that I'm trying to understand.
0
votes
1 answer

why is $k(p-p\bmod z)\bmod p = (kp - kp\bmod z)\bmod p$ true, but only for smaller values of $k$?

Let $p=4295098403$ (tested prime), let $z=65537$ (prime). The following equality: $$(kp - kp\bmod z) \equiv k(p-p\bmod z)\bmod p$$ is true for values of $k<1928$, but false for $k \geq 1928$. This may be a silly question, but what in the world is…
Russ
  • 451
  • 2
  • 9
0
votes
1 answer

Find the value m in modular

Can we find m in this modular? $$aa^{-1} \equiv 1\mod\ m $$ $$where\ a ,a^{-1} are\ known$$
amn89
  • 23
  • 4
0
votes
2 answers

What seat will I be in x steps later?

I need help with the following question regarding modular arithmetic. "A seating plan consists of 7 chairs in a circle. If I am currently sat in chair 3, what chair will I be in $3^{453}$ steps later? Assume that for each step, you move one chair…
Paul H
  • 13
  • 5
0
votes
3 answers

What is the solution for $(x^2- 1) \bmod 8= 0$

I could not figure out the solution of $(x^2- 1) \bmod 8= 0$ Thank you.
Jennifer
  • 11
  • 1
0
votes
1 answer

$a,b,n \in \mathbb Z$. Find the smallest value of $n$ such that $b\mod n = a$

Let $a,b,n \in \mathbb Z$. Find the smallest value of $n$ such that $b\mod n = a$ where $a,b$ are known values and $b > a$. What's the most efficient way to solve such a problem? The naive approach would be choose values of $n$ and increment up…
WHY
  • 248
0
votes
1 answer

Demonstration for method of finding square roots modulo a prime

The Handbook of Applied Cryptography states Algorithm 3.39 for solving $x^2\equiv a\pmod p$ (for prime $p\ge5$ and $\left({a\over p}\right)=+1$ ): Choose random $b\in\mathbb Z_p$ until $b^2-4a$ is a quadratic non-residue modulo $p$, i.e.,…
fgrieu
  • 1,758