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

Tricks for Find Modular Inverses

I know that you can apply Euclid's Extended Algorithm, but I was wondering if there were "tricks" for guessing modular inverses. For example, if you have something like $ 13 \pmod{25}$ then you easily just guess $2$. But if you have something like…
user82004
2
votes
3 answers

A question about modular arithmetic

$2^{35}\equiv x\bmod 561$ I have seen this in my book but there is no solution in it, how can we find x?
AYARcom
  • 364
2
votes
1 answer

Solve for b when $44 \equiv 7 ^ b \pmod{71}$

How do I solve for $b$? $$44 \equiv 7 ^ b \pmod{71}$$ I can only get as far as: $$44 \cdot7^{-1} \equiv b\pmod{71}$$ Although I'm not even sure that that's right.
Jimbo
  • 21
2
votes
0 answers

Why there is no zero-divisors modulo a prime.

Let us say that an integer $k$ where $0< k < m$ is a zero-divisor mod $m$ if $kn \equiv 0 \pmod{m}$ for some $n$ with $0 < n < m$. Prove the following: If $m$ is prime then no integer $k$ is a zero-divisor mod $m$. Homework question; I think I'm on…
2
votes
2 answers

Modulus simplification $(mn) \bmod d = ab$?

I have a modulus question that needs me too prove whether two different statements are true or false. The information I have been given is that: \begin{align} m \bmod d &= a\\ n \bmod d &= b\\ \end{align} \begin{align} m &= dk+a\\ n &=…
2
votes
2 answers

Modulo arithmetic a = 1 mod n

If I know value of $a$ and also it is known that $$a \equiv 1 \pmod n$$ how can I calculate value of $n$?
Rop
  • 339
2
votes
5 answers

Prove they cannot both be integers

Prove that $\frac{21n-3}{4}$ and $\frac{15n+2}{4}$ cannot both be integers for the same positive integer $n$. How to solving this problem?
K.C.S.
  • 183
2
votes
1 answer

Negative quotients and their remainders

Since $16 \div{-3} = -5.\overline{3}$, I thought I could also express this as $16 \div{-3} = -5\:R\:1$ or in other words $16\mod{-3} = 1$. My calculator tells my it is in fact $-2$. Along the same lines, I see that $-16\mod{3} = 2$. So, while the…
2
votes
3 answers

Modular Arithmetic - Quadratic Solutions Problem

I've just been given the following question in my crypto class, and I think I'm fairly sorted for it, but I was just wondering whether there might be any extra solutions to the ones I've worked out. Compute all solutions of $x^2 + 4x - 21 \equiv…
Jack
  • 1,074
2
votes
4 answers

Finding remainder when $32^{32^{32}}$ is divided by $7$

I recently learnt modular arithmetic for finding remainders when huge numbers are to be divided by some number. However, I am stuck at this problem: What is the remainder when $\displaystyle32^{32^{32}}$ is divided by $7$? I suppose the idea here is…
Tejas
  • 2,082
2
votes
1 answer

modulo division of inverse numbers

I am working on some modulo arithmetic and I do not seem to understand why $28^{-1} (mod59)= 19 (mod59)=55$ is and not $28^{-1} (mod59) = 0.0035 (mod59)$ ? When I try to calculate this in Java it does give me 0.0035
2
votes
2 answers

Is the fact that if $x \equiv a\bmod b$ then $x^n \equiv a^n\bmod b$ also true in reverse?

I'm trying to solve the following question: Show that If $x^2 \equiv x\bmod p^k$, then $x \equiv (0\:\text{or}\:1)\bmod p^k$ where $p$ is prime and $k$ is a positive integer. I've managed to get as far as to show that since $p^k|x(x-1)$ then…
2
votes
0 answers

Finding modular variable from some information about multiplications

I have got a very specific mathematic/algorithmic problem. In fact, it is a an automata theory problem(buchi automaton), but this problem seems to be naturaly translated into a modular arithmetic problem. Let $b\in\mathbb N^{>0}$ fixed, and $q$ a…
2
votes
2 answers

Deriving formula for when a number will have a unique cubed root

I have a question as follows and I am pretty sure it is going to come up on my exam Under what condition on $p$ will a number have a unique cube root $\mod p$, where $p$ is a prime number? Derive an explicit formula for finding cube roots when this…
dunika
  • 433
2
votes
2 answers

Evaluate the Cubed Root

So I have a question as follows Evaluate the cube root of $2 \mod 59$ So it is my understanding that I need to find $x$, where $x^3 = 2 \mod{59}$ I have tried different values for $x$ all the way up to $30$ and I still haven't found one that…
dunika
  • 433