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

What is $2018^{2018}$ mod $20$?

The answer is $4$. I saw someone answered in $5$ seconds. How did they do that?
3
votes
1 answer

Splitting congruence equation? $x^2 \equiv x \pmod {b^m}$

I have this equation $x^2 \equiv x \pmod {b^m}$ Now I have found something interesting. I could somehow "split" this, but I don't quite understand if it is always working and how to prove it. Here is what I have done: First I factorize $b$ into its…
3
votes
1 answer

fastest way to calculate the remainder (modular)

I'm creating a computer application in which I need to be able to calculate the remainder of large numbers (more then $30$ digits). I was searching the Internet for the fastest way to calculate this, but no luck. I tried one way: Condition: $\ a \…
3
votes
4 answers

What is $65^{3903}$ $(\text{mod }81)$?

How do you find $65^{3903}$ $(\text{mod }81)$? I found that $65^{3903} \equiv 2 \ \text{ (mod } 3)$ with Fermat's Little Theorem. Is that the right first step? I don't know how I would apply the Chinese remainder theorem here.
3
votes
5 answers

Find the smallest $x$ for $9x \equiv 3 \pmod {23}$

$9x \equiv 3 \pmod {23}$ How to derive the smallest $x$. I understand I can use the extended euclidean algorithm for eg $19x = 1 \pmod {35}$. However, I not too sure how to work on it when it is $3 \pmod {23}$. I am able to reach the step of $1 =…
Jun Hao
  • 317
3
votes
1 answer

How is a minimum defined on $\mathbb{Z}_n$?

If I have a mapping $d(x,y) = \min\{x-y, y-x\}$ where $x$ and $y$ are elements of $\mathbb{Z}_n$, how is this defined? For example, in $\mathbb{Z}_{6}$, $d(0,2) = \min\{-2, 2\}$. Since $-2 \equiv 4 \mod6$ I feel intuitively that the minimum should…
3
votes
1 answer

Modular arithmetic equation system

Assume I have the following modular congruences, where $n = pq$ is the product of two (large) primes: $$A \equiv (xp+yq)^{e_1} \mod n$$ $$B \equiv (zp+uq)^{e_2} \mod n$$ We know $A,B, x,y,z,u, e_1, e_2$ and $n$, but not its prime factors $p$ and…
S. L.
  • 157
3
votes
1 answer

Modular arithmetic in Rabin's cryptosystem

I am working through an example solution in Nigel Smart's Cryptography: An Introduction, 3E, p. 181, about the encryption and decryption of plaintext in Rabin's cryptosystem. The calculation boils down to some modular arithmetic. Unfortunately, I…
H.L.
  • 33
  • 3
3
votes
4 answers

How to solve $ 227x \equiv 1 ~ (\text{mod} ~ 2011) $?

How to solve $ 227x \equiv 1 ~ (\text{mod} ~ 2011) $? I just asked this question, and it seems those methods are not really suitable for large numbers. Please give me some ideas. Thank you.
JSCB
  • 13,456
  • 15
  • 59
  • 123
3
votes
3 answers

Find the last two digits of $2019^{2019}$

Find the last two digits of $2019^{2019}$ I know that you can typically find the last two digits of a number to any power by reducing the number to end with a one and so on (I will show an example of what I am talking about below). However, $2019$…
3
votes
2 answers

modular arithmetic, solving $ax + b \equiv c \pmod d$?

For example $151x - 294\equiv 44\pmod 7 $. How would I go about solving that? The answer says to simplify it into the $ax\equiv b\pmod c $ form first, but I have no clue on how to get rid of the $294$... help?
meiryo
  • 875
3
votes
1 answer

If Euler Totient function fails other methods to find the remainder for the modular exponentiation

Modular exponentiation using Euler Totient Function for the below question. $$ 128 ^{343} \mod 527 $$ using totient function. Is there any other method to find the remainder of the question if totient function fails? Please provide me some valuable…
3
votes
4 answers

Find the smallest positive integer $X$ such that $478^{870} \equiv X \ (\text{mod} \ 273)$

Appreciate if one could advise if my solution is correct. Here is my attempt of the problem: Since $(273, 478) =1,$ by Euler's theorem, $478^{\phi(273)}=478^{144} \equiv 1 \ \ (\text{mod} \ 273) \implies 478^{864} \equiv 1 \ \ (\text{mod} \ 273).$…
3
votes
2 answers

Calculate $20^{1234567} \mod 251$

I need to calculate the following $$20^{1234567} \mod 251$$ I am struggling with that because $251$ is a prime number, so I can't simplify anything and I don't have a clue how to go on. Moreover how do I figure out the period of $[20]_{251}$? Any…
haunted85
  • 1,418
3
votes
1 answer

For a prime of the form $p=2k+1$, show that if $p\!\!\not|a$ and $a\equiv b^{2}\!\!\mod p$, then $a^k\equiv1\!\!\mod p$.

I'm having some trouble with the following question from chapter 1.4 of Beachy and Blair's Abstract Algebra. Let $a,b$ be integers, and let $p$ be a prime number of the form $p=2k+1$. Show that if $p\!\!\not|a$ and $a\equiv b^{2}\!\!\mod p$, then…