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

Prove $\{0 \bmod 2, 0 \bmod 3, 1 \bmod 4, 1 \bmod 6, 11 \bmod 12\}$is a covering system

I'm trying to figure out why $\{0 \bmod 2, 0 \bmod 3, 1 \bmod 4, 1 \bmod 6, 11 \bmod 12\}$ is a covering system. Is there a neat way to prove it?
0
votes
0 answers

modular arithmetic problem puzzle

If you have: $N\equiv 2\mod 3 ,\: N\equiv 3 \mod 4 , \: N\equiv 4 \mod 5 $ What is N?
Papa
  • 483
0
votes
2 answers

$c \in \mathbb{N}$, so that $c \cdot 11 = 23 \mod 103$

How can one find $c \in \mathbb{N}$, so that $c \cdot 11 = 23 \mod 103$? I know that $a \cdot b \mod n = (a \mod n \cdot b \mod n) \mod n$. Furthermore, Fermat's little theorem says that for all prime $p$ and if $p$ does not divide $a$ $a^{p-1}…
0
votes
2 answers

Solving an equation mod $n$

Part of a solution, I'm trying to calculate $(n-1)^2$ in $mod\ n$ when $n\in\mathbb{N}$. What I tried to do: $$ (n-1)^2=(n^2-2n+1)\ (mod\ n)$$ But I'm not sure what to do next. How should I approach this?
vesii
  • 1,979
0
votes
0 answers

Order of [11] in $\mathbb{Z_{335}^x}$

Order of [11] in $\mathbb{Z_{335}^x}$. What I did is: Since, GCF(11, 335) = 1 So, I thought $11^x \equiv 1 \pmod {335} \Rightarrow 11^{\phi(335)} \equiv 1 \pmod {335}$ $x = \phi(335) = 264$ But when I tried it in Wolfram alpha x = 66(n).
0
votes
2 answers

how do I apply repeated squaring on this modulo expression?

$3^{10^{100}} \pmod {13}$ It was originally $(10^{100})^{(10^{100})}$ (i.e. googol^googol), but I simplified it down to what I have there. However, I can't seem to reduce the exponent without changing the value of the entire expression. I was…
bobbyjeo2
  • 110
0
votes
3 answers

Do decimals exist in any Z? (Z as in integer modulo n)

For example, if I'm in Z5, $-2$ is equivalent to $3$ which is equivalent to $8$. Also, the value of $x$ in the equation $4x = 2$ is $3$. Note how any integer can be written as an integer that is within $\Bbb Z_5$ (ex. $-2$ and $8$ can both be…
James Ronald
  • 2,331
0
votes
1 answer

Solving a congruence equation using a corollary of Fermats Little Theorem

I have the congruence equation $$4x=11 \mod{19}$$ How can I solve this using $$x\equiv a^{p-2}b\mod{p} $$ Any pointers would be greatly appreciated!
THN
  • 137
0
votes
1 answer

Rational power in modular arithmetic

I was going through Batch RSA and in one such case they have used\ t = $\ m^x$ mod n where x is of the form 1/e where e is an integer. what does t mean and will it be an integer ? Eg if m = 10, e = 2 and n = 100 then will t = $\sqrt10$ mod 100 or…
Prajval M
  • 101
  • 4
0
votes
3 answers

Find the residue by dividing $1^5+2^5+....+1080^5$ by 14 using congruences.

I want to find the residue by dividing $$1^5+2^5+....+1080^5$$ by $14$. Im supossed to attack this problem by using congruences but Im not pretty sure how to do it. All I know is that if $14 | 1^5+2^5+....+1080^5$ then…
Cos
  • 1,799
0
votes
1 answer

Find all integers x with pulverizer. Two congruences included

$ x ≡ 5 (mod 11) $ $x ≡ 6 (mod 9) $ Which integers $x$ is between $0-300$ that fulfills this two congruences? I think I got this right but I am not quit sure how to find all x's. This is my solution: $x ≡ a(mod m1): m1=11$ $x ≡ b(mod m2): …
0
votes
1 answer

Using order of $a$ to show that $n \equiv 1 \mod p$

We are given that $n$ is a prime number. Additionally, $a^p \equiv 1 \mod n$ where $p$ is a prime and the order of $a$. How can I show that $n \equiv 1 \mod p$?
user608500
0
votes
2 answers

Given $n$, find $a$ and $b$ such that ${a \mod b = n}$

Let's assume I am given a positive integer $n$, as well as an upper limit $L$. How could one find all, or at least one, possible solutions for $a$ and $b$ such that ${a \mod b = n}$ where as $0 <=a, b <= L$?
766F6964
  • 113
  • 5
0
votes
1 answer

Modulo operation on fractions

I am not sure if I understood the modulo operation on fractions properly. Therefore I want to ask if someone can provide me an intuitive visualization with an real-world analogy, in which that operation is can be applied (like the clock for the…
0
votes
1 answer

Solve system of congruences which involves a quadratic term

I am studying for an admission exam and I came to this system of congruences $$x^2 \equiv 2 \text{ mod } 7 \hspace{1cm} x \equiv 1 \text{ mod } 5 $$ I know how to solve linear systems, but I don't know what to do with a quadratic one. Could anyone…
Santiago
  • 186