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
4
votes
3 answers

Proving $93x + 47 \equiv 61 \pmod {101}$

I am preparing for an exam. I am dealing with this right now: $$93x + 47 \equiv 61\pmod{101}$$ However, I can't figure it out. Can someone describe steps for this example, or provide a link to any free pdf, website describing this problem and the…
4
votes
3 answers

How Can I prove (a+b) mod m = (a mod m) + (b mod m)) mod m?

modular arithmetic How Can I prove (a+b) mod m = (a mod m) + (b mod m)) mod m ?
4
votes
2 answers

Given $a\equiv x\pmod p$ and $b\equiv y\pmod q$, can we deduce a congruence relating $a,b,c,y$ modulo $pq$?

Assume that \begin{align*} a &\equiv x \pmod p \\ b &\equiv y\pmod q.\end{align*} Does this imply an equation involving the numbers $a,b,x,y$ modulo $pq$? One possible example would be $$ab \equiv xy\mod pq$$
Malice
  • 187
4
votes
1 answer

How to apply modular division correctly?

As described on Wikipedia: $$\frac{a}{b} \bmod{n} = \left((a \bmod{n})(b^{-1} \bmod n)\right) \bmod n$$ When I apply this formula to the case $(1023/3) \bmod 7$: $$\begin{align*} (1023/3) \bmod 7 &= \left((1023 \bmod 7)((1/3) \bmod 7)\right)…
Paul Lo
  • 187
3
votes
2 answers

Proving divisibility by 7 using modular arithmetic

Prove that $2222^{5555} + 5555^{2222}=0 \pmod{7}$. I'm not getting how to start away with this problem. I know that modular arithmetic should be used. Please give me some hints on how to solve this question. I don't expect complete answers as I…
3
votes
5 answers

Solve $85x \equiv 34 \pmod{153}$

I'm not exactly sure how to solve these modular problems involving a variable. Can someone solve this (trivial) example with explanation? I found the answer (4) by trial and error, however, I'm sure this isn't the most efficient approach. Help?
3
votes
3 answers

How to prove that $a+b$ is a multiple of $24$?

Let $x$ be an integer one less than a multiple of $24$. Prove that if $a$ and $b$ are positive integers such that $ab=x$, then $a+b$ is a multiple of $24$.
K.C.S.
  • 183
3
votes
3 answers

Find a number congruent to mod

Can anyone give a hint of how to go about solving this? Please don't give answer thanks Find the integer $a$ such that $a \equiv 99 \pmod{41}$ and $100 \le a \le 140$ We did not go over this in class and can really use some start up ways. I know 99…
3
votes
2 answers

Hint for finding the remainder when $2018^{2019}$ is divided by 13

I have been thinking of how to answer this. The question is find the remainder of: $$\frac {(2014^{2015}) \space (2016^{2017}) + 2018^{2019} \space}{13}$$ This is what I was thinking: Since $ 13 \space|\space 2015 $, we know that: $2014 \space…
3
votes
1 answer

Deduce the value of a number by only apply modulo operation

For an unknown 16 bit number U, an N (8 bit) modulo operation can applied, which results in a known 8 bit number R. The value N must be: 128 >= N >= 255. How do I find U, or at least as much as I can? The first 7 bytes can be obtained by U mod (2^7)…
kirill
  • 145
3
votes
3 answers

Trying to remove a mod from an equation.

$376$ is a number that for positive integers $n$, $376^n$ will always end with the number $376$. Now knowing that $376^k \mod 1000 = 376$. How do you prove that the following is true. $$ 376^k \mod 1000 = 376^{k+1} \mod 1000 $$ Is there a way to…
Tim
  • 33
  • 1
  • 4
3
votes
0 answers

Is the modulo operation a standard mathematical operation which actually means Euclidean division?

I was having this long discussion with a colleague as to whether the Modulo operation is a standard mathematical operation or not. He insisted the programming languages don't have a defined standard for the sign of the operation because it's not…
3
votes
5 answers

calculating mod 7

Problem: Calculate $10^{10^{10}} \pmod 7$ According to Fermat's little theorem: $a^{p-1}\equiv1 \pmod p$, so $10^6\equiv1 \pmod 7$ and $10^n\equiv4 \pmod 6$, $n$ being any integer, why can we write $10^{10^{10}}\equiv10^4 \pmod 7$? Similarly, if…
user59768
  • 105
3
votes
3 answers

If $a=a'$ mod $n$ and $b=b'$ mod $n$ does $ab=a'b'$ mod $n$?

So far this is my working out: $n|a-a'$ and $n|b-b'$ So $n|(a-a')(b-b')$ Expanding: $n|ab-a'b-ab'+a'b'$ I'm not sure what to do next. I need to show that $n|ab-a'b'$
user112773
  • 81
  • 5
3
votes
1 answer

modular arithmetic with large numbers

I am having trouble finding a number where 579^$65$ is congruent to x mod 679 and x has to be less than 676. i did the trick of 2's and got: $579^2$ $\equiv$ 494 mod 679 $494^2$ $\equiv$ 275 mod 679 $275^2$ $\equiv$ 256 mod 679 $256^2$ $\equiv$ 352…