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
1
vote
3 answers

Reducing powers in modulo arithmetic

I am working through a modulo tutorial and have become stuck here: $$ 11^{32}(\operatorname{mod}13) = (11^{16})^2(\operatorname{mod}13)= 3^2(\operatorname{mod}13)= 9(\operatorname{mod}13) $$ My question is, how does…
Jason
  • 13
1
vote
5 answers

Show that $a^{25} \pmod{88}$ is congruent with $ a^{5} \pmod {88}.$

Show that $a^{25} \pmod{88}$ is congruent with $ a^{5} \pmod {88}.$ I have proved it in the case that $\gcd(88,a)=1$, but in the other case , I don't know it. Any ideas?
bob
  • 1,256
1
vote
5 answers

Calculate $2008!\pmod {2011}$

I think you should use the theorem of Wilson, because 2011 is a prime number. But I don't know how to use it. Thanks
bob
  • 1,256
1
vote
2 answers

Assume $p \equiv3 \pmod 4$ and $n \equiv x^2\pmod p $. Given $n$ and > $p$, find one possible value of $x$.

The exercise verbatim: Assume $p \equiv3 \pmod 4$ and $n \equiv x^2\pmod p $. Given $n$ and $p$, find one possible value of $x$. (Hint: Write $p$ as $p = 4k +3$ and use Euler's Criterion. You might have to multiply two sides of an equation by…
1
vote
3 answers

Congruence $320 \equiv 1 (\text{mod }x)$

I have the following congruence $320 \equiv 1 (\text{mod }x)$ And the question is : find all the modulos $x$ that make this congruence true.
lopata
  • 319
1
vote
2 answers

Proof of a congruence relation

Let n∈N, and let a,b∈Z. Suppose that a≡b (mod n). Prove that n|a if and only if n|b. As can be proceed?
Jianluca
  • 379
1
vote
4 answers

Why $0$ in number $50$ is not a significant digit?

I have been reading definitions of significant figures which vary from source to source. 1-The digits in a number that indicate the accuracy of the number are called significant figures or digits---College Algebra by Raymond A. Barnett and Micheal…
Sufyan Naeem
  • 2,298
1
vote
4 answers

How to solve modular equations

How to solve modular equations? So for example $a \equiv i$ mod $x$, $a \equiv j$ mod $y$ for some given $i,j,x,y$ with $gcd(x,y)=1$, and I must find $a$ mod $x*y$. Any tips on how to do this? Specifically I want to calculate $a \equiv 1$ mod $16$,…
1
vote
3 answers

What is the following expression simplified to?

$$x \mod 1000 \mod 5$$ I would have thought that it was $x \mod 5000$ except that it doesn't hold true for $x = 5005$ since you'll get zero, but $5005 \mod 5000 = 5$.
Don Larynx
  • 4,703
1
vote
1 answer

Can modulo(remainder) be distribute over division?

Let $a\%b$ be the modulo operation, returning the remainder of $a$ when divided by $b$. Is it true that: $$\left(\frac{a}{b}\right)\% 5 = \frac{(a\% 5)}{(b\% 5)}$$ For instance, for $a=10$ and $b=2$ we…
hii
  • 11
1
vote
1 answer

Is there any modular arithmetic property relating $\mod mn$ to $\mod m$?

We know that addition, subtraction and multiplication can be defined for integer modular arithmetic: for $a \equiv b \mod n$ and $c \equiv d \mod n$, $a+c \equiv b+d \mod n$ and so on. But is there any modular arithmetic property that relates $a…
mod
  • 11
1
vote
2 answers

Modulo operations over Gaussian Integers

Given $a,b\in\Bbb Z[i]$, is there a definition and calculation of remainder $a\bmod b$? Could you provide examples say $35\bmod (2+3i)$, $(43+7i) \bmod (22+8i)$?
Turbo
  • 6,221
1
vote
3 answers

Modular arithmetic $x \equiv 17^{12} \pmod {11}$

I'm trying to evaluate $x \equiv 17^{12} \pmod {11}$ using modular arithmetic, but I'm a bit lost. I'd really appreciate a step-by-step on how to do it. Thanks!
1
vote
2 answers

Q: simple modular arithmetic

I am trying to solve a programming problem but am stuck on some modular algebra. The equation I am trying to solve boils down to $$a \equiv (b + cx)\pmod {10^9+7}$$ where I know a, b, and c and need to solve for x. Is there a way to do this? Sorry…
1
vote
1 answer

Modular Arithmetic - Finding q

I am having trouble comprehending the following problem: In mod $n$ arithmetic, the quotient of two numbers $r$ and $m$ is a number $q$ such that $mq = r$ mod $n$. (The author mentioned before that he represents $\equiv$ with $=$). Given $r$, $m$,…
mrQWERTY
  • 595