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 solve $ab\bmod c = d$

How can $ab\bmod c = d$ be solved, if $b$, $c$ and $d$ are known? A similar algorithm is used by LCGs (weak PRNG) to give random values. To solve this, I used WolframAlpha which quickly solved, but shown nothing about process. What is the process to…
iovoid
  • 101
0
votes
3 answers

How to compute large modulos with pen and paper?

I would like to compute $47^{9876543210} \bmod 9$ and $48^{12345678901234567890} \bmod 9$ with pen and paper. I know this is similar to computing $2^{9876543210} \bmod 9$ and $3^{12345678901234567890} \bmod 9$ I also noticed that 987653210 is…
0
votes
2 answers

calculate with large exponents

Can somone explain me, how I can check if an number is an divisor of a sum with large exponents? Something like this: Is $5$ a divisor of $3^{2012} - 4^{2011}$? And how can I calculate something like that: $39x \bmod 680 = 1$. Thanks for your…
Tim
  • 3
0
votes
1 answer

Derivation of Calculation in Modular Arithmetic Theorem

I'm confused on their calculation and how they arrived at their calculation that on the second line of the image below:
user459897
0
votes
2 answers

Value of second last digit

How can I find the second last digit of the number $7^{41^{17}+1}$? I'm not quite sure how to start. A hint would suffice. Thanks!
simp
  • 883
0
votes
1 answer

Modular equation

I have this expression: $\tau=a+b \mod x$ and from this I want calculate $b$. From my side I obtain that $b=\tau \mod x - a \mod x$ but the solution is: $b=\tau - a \mod x$. Why ? I don't understand.
CipherX
  • 105
0
votes
2 answers

Remainder for negative fraction division

What will be the remainder for the following division and what is the generale rule applied to it: $$ (-25)^{-1}\; mod\; 26 \;$$ ?
k1gabi
  • 13
0
votes
1 answer

Calculating modulo of 7 using bitshift and addition

I'm hoping this question is ok here. It is in the context of programming, perhaps a bit simple for this audience, and a lot of the discussion here is far beyond me. I'm trying to calculate modulo 7 using bitshift and addition according to this blog…
0
votes
1 answer

Is this $0$ in $\mathbb{Z}/n^2\mathbb{Z}$?

This question is related to 3-cocycle in $\mathbb{Z}/n\mathbb{Z}$ Let $a,b,c,d\in\mathbb{Z}/n\mathbb{Z}$. Is $a(b-d+[c+d]-[b+c])$ equal to $0\mod n^2$? Here the $[b+c]$ notation means $b+c\mod n$. I cannot think of any counterexamples, yet I do…
0
votes
4 answers

How to solve $30^{37} \mod 77$ without calculator?

I tried doing something like this: $$(30^2)^{15}(30^7)\mod 77$$ but it is not effective, maybe someone knows some tips and tricks to solve this ?
0
votes
2 answers

How would I determine if there is at least 1 integer that can satisfy 5 congruences all at once?

How would I determine if there is at least 1 integer that can satisfy 5 congruences all at once? Would I prove it individually? For example A->B->C->D->E->A
Anthony
  • 177
0
votes
0 answers

How to find such modular division answer?

Let $x = a\bmod M, y = b\bmod M$, where $M$ is a prime number. I do not know $a$ and $b$, but I know $x$ and $y$ and $M$. Is it possible to calculate $ (a/b)\bmod M $? Sorry if it sounds too junior
shole
  • 173
0
votes
1 answer

How to find the least integer in modular arithmetic?

I am new to modular arithmetic, so I was reading multiple articles on the web. This khanacademy page describes it very intuitively. However, I have one query for the below equation: $$A\mod B = (A+K.B)\mod B$$ Is there a mathematical way to find the…
user3243499
  • 369
  • 5
  • 16
0
votes
3 answers

Show that for every odd integer, $n^3 - n^2 - 5n +5$ is divisible by 8 using modulo arithmetic

Problem: Show that for every odd integer, $n^3 - n^2 - 5n +5$ is divisible by 8. using modulo arithmetic I'm not sure how to use the modulo arithmetic concept to answer this question.
Jdinh98
  • 33
0
votes
2 answers

Dividing in modular equation?

Does $ac\equiv ab \pmod{ad}$ always imply that $c\equiv b \pmod d$ ? If this is not always the case, then when is it ?