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

Divide after taking mod

There's probably a formal way to put this with rings, but suppose I have a number x and mod base M and divisor d. I know x mod M = x', and that d is divisible by x. How do I find x/d mod M? It seems possible because if you take x = 12, M = 5, d = 3…
0
votes
0 answers

Determine the solution of congruence equations

how would we determine the solution of 4x≡1 (mod 27) which is specifically negative and closest to 0. I know we first get the gcd, but what do we do after that?
0
votes
1 answer

Modular arithmetic $7^{60} \pmod{77}$

How do you solve $7^{60} \pmod{77}$? For $5^{60} \pmod{77}$, it's equal to $1$ because I think the $\gcd(5,77) = 1$ and using the FLT we can find that $5^{(7-1)(11-1)} = 1 \pmod{7*11}$. But how do you get $56$ from $7^{60} \pmod{77}$?
0
votes
1 answer

proof $x-1$ is always invertible in $\mathbb{Z}_{^3}$.

in $a\in\mathbb{N}$ we know that $x>1$. How can I prove the question above? I see the proof from this question, $x+1$ is always invertible in $\Bbb Z_{x^3}$. But is the answer the same when the sign is just flipped?
user862303
0
votes
0 answers

How to solve congruence equations with powers?

I'm wondering if there are efficient methods to solve equations such as: $$ x^{30} = 7 \pmod{83} $$ Where the exponent is some arbitrarily high number. Thanks!
derp
  • 1
0
votes
0 answers

Solving $(x + a_i)$ mod $n_i \equiv 0$ for $x$

The typical system of congruence equations addressed by the CRT looks like $$ x \equiv a_i \text{ mod } n_i $$ Is there a way to use those or similar techniques to tackle something of this form? $$ (x + a_i) \equiv 0 \text{ mod } n_i $$
Palace Chan
  • 1,237
0
votes
0 answers

Find first common number where X mod Y == 0 for a set of numbers

I apologize if the question is confusing, I don't know how else I could ask it. This is a programming related task but since the question I have is mathematic in nature, I figured I'd ask the question here. I have a set of $9$ unique numbers where…
Karl S.
  • 101
0
votes
0 answers

Is there a specific name for this process?

Problem Statement: You have 9 dollars. The store sells sandwiches for 5 dollars, drinks for 3 dollars, and chips for 1 dollar. If you want to spend all of your money and exit the store with the least amount of items, how much of each item should…
O.S.
  • 592
0
votes
0 answers

Question with modular arithmetic

I was given this question A store sold $72$ decks of cards for $\$a67.9b$, where $a$ and $b$ are digits. Find $a + b$. I'm not really sure how to solve this. I tried $100a + 67.9 + b \cdot0.01 \equiv 0 \pmod{72}$. From there you can get $100a + b…
user776935
0
votes
1 answer

How do I prove that there are no repeating integers and all numbers from 0 to b-1 are present?

While messing with modulus in python, lomod = [num % 27 for num in [i * 8 for i in range(27)]] print('Unsorted:', lomod) lomod.sort() print('Sorted:', lomod) I found something interesting. For $a,b\in\mathbb{Z}$, and $a,b$ are relatively…
0
votes
0 answers

Definition of a solution to a modulo

I have the following statement to prove, for homework: If $r ∈ \mathbb{z}$ is a solution to $ax ≡ b ($ mod $m)$, then $r + mk, k ∈ Z$, are also solutions to $ax ≡ b ($ mod $ m)$. What does "$r ∈ \mathbb{z}$ is a solution..." mean? I assume it means…
mathjohnn
  • 181
  • 11
0
votes
5 answers

Remainder of division when $p$ is not prime

Calculate the remainder of the division of $1160^{602}$ by $35$. What I thought of doing right away is to factor out $602$ until I get to a point where I can apply Fermat's theorem. However, $35$ is not a prime number. How to proceed in this case?
gmn_1450
  • 519
0
votes
2 answers

Conguences with power

Determine all the solutions of the congruence $5x^{44} ≡ 9 \pmod{29}$, using the index in base $2$ module $29$. I don't know how to proceed with the presence of this $5$ by multiplying the $x$ ... should I multiply by the inverse class to eliminate…
gmn_1450
  • 519
0
votes
2 answers

residue class rings - value calculations with modulo

computer science studies - residue class rings. I have to calculate the following expression in $ \mathbb{Z_9}$ and the other one in $ \mathbb{Z_{16}}$ my question is how one should handle $-1, 23, 10$ in the "powers"? are they really powers or do…
Ozk
  • 429
  • 2
  • 10
0
votes
1 answer

Solve the equation in $\mathbb{Z}_{7}$

The problem is taken from my textbook in algebra and is given as: Solve $x+4=3$ in $\mathbb{Z}_{7}$ From the euclidean algorithm I found that $2=4^{-1}\bmod(7)$ Now I'm not completly sure how to continue but I tried: $$x+4+4^{-1}=3+4^{-1}…