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

How to show $h\equiv 1\bmod{(p-1)(q-1)(r-1)}\implies a^h\equiv a \bmod{pqr}$?

Let $p, q, r$ be distinct primes, let $n = pqr$, and let $m = (p − 1)(q − 1)(r − 1).$ Show that for any $a\in \mathbb Z$ and $h\in \mathbb N$, we have $(h\equiv 1\mod m)$ implies $(a^h\equiv a \mod n).$ I know I need to approach this with Fermat's…
Robin
  • 33
0
votes
0 answers

Modular Arithmetic Simplify

Congruence is an equivalence relation so transitive, so $\,x^2\equiv 79,\ 79\equiv 2\Rightarrow x^2\equiv 2,\,$ see the linked dupe. I was wondering how in number theory we are able to determine how to quickly simplify modular congruences. So for…
yfm
  • 35
  • 2
0
votes
0 answers

All values of $x$

So I just learned about modular arithmetic today and I was solving a system of congruences probably that you saw before. the statement was $n ≡ 3\pmod5$ $n ≡ 1\pmod 7$ $n ≡ 6\pmod8$ writing this again as $$5x + 3 = 7y + 1 = 8z + 6$$ and trying to…
user1172521
0
votes
0 answers

Is there an efficient way to find x given mod(ax;b)=c?

It'll be the same thing as solving ax+by=c. There's an algorithm to find gcd(x;y) with it you can solve that equation but it is very long for some pairs of numbers. Of course a,b,c,x,y are all integers and a,b,c are known
0
votes
1 answer

Modular arithmetic on $ 2x^3 - 7y^3 = 3 $

Find integers x and y such that $2x^3-7y^3=3$ How to do it? My first thought was to reduce it to one variable problem by taking suitable mod. 1) mod 7 $ 2x^3\equiv 3 \bmod 7 $ 2) mod 2 $ y^3\equiv 3 \bmod 2 $ How to solve it?
H.E
  • 2,056
0
votes
0 answers

What are the required condition for $a^b \mod c$ to cycle through all number between $0$ and $c$ as the value of $b$ increases?

For example, $3^b \mod 5$ will cycle through all number between $0$ and $5$: $3^1 \mod 5 = 3$, $3^2 \mod 5 = 4$, $3^3 \mod 5 = 2$, $3^4 \mod 5 = 1$, $3^5 \mod 5 = 3$ Another example is $11^b \mod 13$, $2^b \mod 5$, $3^b \mod 7$ Example of modulo…
LLL
  • 103
0
votes
1 answer

Why is modulo value correct.

I have come across programming questions where the output is requested as modulo 10^9+7 or some other prime number. My confusion is that why is the value returned by performing modulo operation considered as the correct answer. If for example 3!= 6…
Shivam...
  • 155
0
votes
0 answers

Does congruence mod k work for exponents?

For $\text{mod 5}$, $[1] = \{\dotsc, -4, 1, 6, \dotsc\}$ So, we can write, $$6\equiv1\ \text{(mod 5)}\tag{1}$$ Which means that I can substitute $1$ for $6$ (and vice versa) anywhere I see it $(\text{mod 5})$. So, consider the example…
0
votes
0 answers

Possible solutions for n * 50886 = r mod (70001)

Let n be all natural numbers, n = 1, 2, 3, ... How to find all possible remainders in n * 50886 = r mod (70001)? I calculated all possible values for r up to 50886. They are: 50886, 31771, 12656, 6197, 5935, 5673, 5411, 5149, 4887, 4625, 4363,…
0
votes
1 answer

Given $a$ and $b$, find $n$ such that $a \equiv b \pmod{n}$

Given two values $a$ and $b$, is there an equation/algorithm that can efficiently find $n$ in the following equation? $$a \equiv b \pmod{n}$$ I found this question while looking for an answer, but it's the inverse of what I need. Edit: I'm not sure…
0
votes
0 answers

How to solve the equation $3x=33 \pmod{100}$?

The equation is $ 3x\equiv 33\pmod{100}$ I factored the 100 as $2^2 \cdot 5^2$ then I got the system of equations: $$3x \equiv 33\pmod 4$$ $$3x \equiv33\pmod{25}$$ then I transformed the equivalences into this two: $$3x \equiv 2 \pmod 4$$…
0
votes
2 answers

Congruence cancellation [in Hensel lifting a square root to a $p$-adic root]

In the book of [Z.I._Borevitch,_I.R._Chafarevitch]_Théorie_des_nombres p.21 the authors talking about the construction of 7-adic integers by considering equations of type $$(C_n): x^2\equiv 2\mod 7^n$$ for $n=1$ the solution satisfy $x_0\equiv \pm…
0
votes
1 answer

Congruence with power two less than a prime modulus

We know from Fermat's little theorem that $$ 15^{42} \equiv 1 \mod{43} $$ since 43 is a prime number and $43 \nmid 15$. Could I use this fact to calculate $15^{41} (mod\ 43)$? My first impression tells me that I can not divide by 15, since is 15 is…
Nick
  • 332
  • 2
  • 8
0
votes
1 answer

How do I find $11^{339} \pmod {19}$? Modular Exponentiation

I'm trying to work out a question found in my textbook for college on modular exponentiation, {11^399 mod 19}. These are the steps I took: 11^399 mod 19 8^339 mod 19 [19 - 11 = 8] (8^388 * 8) mod 19 [subtracted the exponent by 1 and multiplying the…
0
votes
1 answer

Counting points where two modulus functions meet

I have two points A & B rotating around some pivot P. They start at 12 o'clock and start rotating clockwise around P simultaneously with different constant velocities ($s_A$ and $s_B$). The speed of $1$ is exactly 1 circle per second. I'm treating…