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
2 answers

How to calculate $5^{2003}$ mod $13$

How to calculate $5^{2003}$ mod $13$ using fermats little theorem 5^13-1 1 mod 13 (5^12)^166+11 mod 13 a+b modn=(a modn + b modn) modn (1+11mod13)mod13 12 mod 13 = 12 why answer is 8 ? how do we calculate this thanks
rektandlove
  • 11
  • 1
  • 5
0
votes
2 answers

Exponent Modulo of $3^{27} \mod 10$

The original question is: $3^{3^3} \mod 10$ I got to $3^{27} \mod 10$ Then did the following: $3^1 \mod 10 = 3$ $3^2 \mod 10 = 3^2 \mod10 = 9 \mod 10 = 9$ $3^4 \mod10 = 9^2 \mod10 = 81\mod10 = 1$ <-- This is where I get stuck. Could someone explain…
Monil
  • 43
0
votes
2 answers

Simplifying two simultaneous modular arithmetic equations

For example, say I have two equations for $n$: $n\equiv 1 \mod 2$ and $n\equiv 1 \mod 3$ I can show that $ n \equiv 1 \mod 6$ by saying that: $n \equiv 1, 3, 5 \mod 6$ and $n \equiv 1, 4 \mod 6$ using the previous two equations, and then seeing…
Ronikos
  • 596
  • 1
  • 4
  • 14
0
votes
3 answers

How to Solve 3x+9 is congruent to 8 mod 11?

I need five solutions to the above problem, but I'm not sure where to start with this.
0
votes
1 answer

Modulo arithmetic rule

I remember that: $ab \equiv n \pmod p$ can be written as: $((a \text{ mod } p) \cdot (b \text{ mod } p)) \text{ mod } p = n \text{ mod } p$ Applying the modulo to the factors of the product and I found PDFs calling this "Homomorphic Rule"…
0
votes
2 answers

Simplification of Modulo formula

I believe that this: $$(5^3 \mod{57})^5 \mod{57}$$ is the same as: $$(5^3)^5 \mod{57}$$ But what is the logic of this simplification?
whytheq
  • 237
  • 1
  • 7
  • 12
0
votes
2 answers

Time complexity for mod operation.

Let $x,y,n$ be $1234567809,12345,9087654321$. My laptop can perform $1$ $64$-bit integer mod operation in $1$ microsecond. Estimate the number of seconds needed for each of the following: Find $x^y\pmod n$ Find $t$ such that $x^t=2672633475\pmod…
Heyo
  • 167
0
votes
0 answers

Determine integer given residues modulo p_n1, p_n2 etc?

Suppose you know an integer is congruent to, say, $a \pmod 2$, $b \pmod 3$, $c \pmod 5$, $d \pmod 7$, $e \pmod {11} $, is there a method to determine the least such integer? There is, of course, one such integer every 2*3*5*7*11 integers. Note…
0
votes
1 answer

proof of theorem related to modular arithmetic

before i will explain of my question , first of all let us introduce classical definition of division algorithm ,namely for given integer $a$ and integer $d$, here exist unique integers $q$ and $r$ such that $0 \leq r
0
votes
3 answers

Prove that $n^4$ is congruent to 0 or 1 modulo 5

Prove that $n^4$ for all $n\in{\mathbb Z}$ is congruent to 0 or 1 modulo 5. Hint from professor: Do so using different cases. I am confused on how to prove this for all $n$. I understand that you can test a few numbers but I am stuck on how to show…
0
votes
1 answer

Negative remainders (modulus)

Say I want to calculate say 12 (mod 13). Can I do the following: swap 12 and 13 and say that since 13 (mod 12) = 1, I can therefore conclude that 12 (mod 13)= -1? If not, could someone please explain the correct procedure were I can get negative…
user367872
0
votes
1 answer

Help understanding some solution for a module

I'm trying to solve the following Determine if $a^3=-9$ is solvable in $\mod 31$ and in $\mod 11$. So I did the following, for $a^3-9$ we have that $$a^3=-9=22\mod31$$ from there I'm not quite sure how to continue. I know that for that it must…
0
votes
3 answers

How to solve congruence for quadratic equation $3x^2+x+1 = 0$ over $Z_5$?

Solve $3x^2+x+1 = 0$ over $Z_5$. Essentially, the equation needs to be solved over $\mod5$. Frankly, I don't really have an idea how to start. The problem is that I have and $x$ and $x^2$ and I don't see how to single the $x$ out. I could've…
Yos
  • 2,663
0
votes
0 answers

The smallest integer divisible by 2004

The smallest positive integer divisible by $2004$ and writing in base ten with the only digits $2$ and $4$ is $222 444$. What is the next? And the next of the next?
0
votes
0 answers

decoded and encoded text are not equal to each other

i know that it is related to the programming a bit more, but i think mathematical issue as well, for instance there is given my code function result=affine_cipher_encode(a,b,m,s) %a and b are prime numbers % m=total number of letters…