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
1 answer

Using Fermat's Little Theorem for remainders

Using Fermat's little theorem, we know that $$k^{p-2} \cdot k \equiv 1 \pmod p.$$ To find the multiplicative inverse of $6$ modulo $17$, we need to calculate $6^{15} \pmod {17}$. It's supposed to be all congruences hold modulo $17$. $$6^{15} \equiv…
0
votes
1 answer

$xa \equiv ya \pmod p $ implies that $x \equiv y \pmod p$

We are working in the set of integers. For $x,y,p,a$: $$x \equiv y \pmod p \implies xa \equiv ya \pmod p$$ When can we also assume the following? $$ xa \equiv ya \pmod p \implies x \equiv y \pmod p $$ Another way to ask the question is to prove that…
0
votes
1 answer

Why is it that for three numbers $i, j, n \in \mathbb{N}$, if $i \equiv j \pmod{n}$ and $i, j \leq n$, then $i = j$?

For $i, j, n \in \mathbb{N}$, if $i \equiv j \pmod{n}$ and $i, j \leq n$, then $i = j$. Might be a trivial question, but I don't see why this holds. Can someone explain to me why this is true?
user799269
0
votes
1 answer

How to solve such a set of congruency?

I came across a question like this having multiple sets of congruency where a value was congruent to $1 \pmod n$ and then at last it was a multiple of $k$. So, was thinking if there is any general way to solve this without going through every line,…
Asv
  • 500
0
votes
2 answers

Using Mods to show something is divisible by 3

How do you show $5^{2 \cdot 3^k}-5^{3^k}+1$ is divisible by $3$ using mods? I tried to simplify to $2^{2 \cdot 3^k}-2^{3^k}+1$, but now I am stuck.
user797346
0
votes
1 answer

Modular arithmetic: congruence equation problem

We have the following congruence equation: $$10x \equiv 8 \mod (59)$$ I was requested to solve this using the Euclidean method. First I noticed the $gcd$ of $10$ and $59$ is $1$, which means the equation will have a solution (for $1$ divides any…
lafinur
  • 3,322
0
votes
1 answer

Prove that 91 is pseudoprime to base b.

I'm quite stuck on this question and would really appreciate anyone who's able to explain the way it's worked out to me! The full question is 'Let b be an integer coprime to 91. Assume that b is a quadratic residue modulo 91. Prove that 91 is…
user795056
0
votes
1 answer

Result of number with decimal point modulo $10$.

This is a very simple question, very trivial to many, but I have to resolve this doubt! I have done the division $2.2/10$ by hand, and the result is $0.22$, without any remainder: But why if I do with calculator, I obtain this: $$2.2 \mod 10 =…
JB-Franco
  • 852
0
votes
1 answer

Prove that $S$ is the number of integers congruent to $n$ mod $p$ between $a$ and $b$ inclusive where $a,b$ are integers

This question has already been answered on another question although the answers are not correct. However, thanks to the comments, I was able to find a formula. Here it is: $T=n-a+p\lfloor\frac{b-n}{p}\rfloor$ $S =\lfloor\frac{T}{p}\rfloor+1$ So we…
0
votes
2 answers

How does this iterative method of computing $n! \bmod m$ work?

I found this snippet of code that calculates $n! \bmod m$ iteratively. long long x = 1; for (int i = 2; i <= n; i++) { x = (x*i)%m; } cout << x%m; Now, I'm still new to modular arithemtic. I know that $(a\cdot b) \bmod m = (a \bmod m \cdot b \bmod…
user821
  • 124
0
votes
1 answer

Calculate the remainder of $11^{2020} / 7$

I tried to get a pattern by doing $11^1 / 7 = 1 , r=4$ $11^2/7 = 17, r=2$ $11^3 / 7 = 190, r=1$ but the numbers keep getting larger and larger and I think this is not the way to go about this problem. Can someone please explain the correct way on…
Gruja
  • 107
0
votes
3 answers

Prove that for any n, $[k]_n$ is invertible in the ring $\mathbb{Z}_n$ if and only if $n$ and $k$ are relatively prime.

I have trouble proving the above statement. Here is my approach. First, I prove that if $n$ and $k$ are not relatively prime, it implies that $[k]_n$ is not invertible. If $n$ and $k$ are not relatively prime, there exist $g \neq 1$ such that…
slhulk
  • 270
0
votes
2 answers

Can someone please help me out with this modular arithmetic problem?

I've been trying to see how to calculate this math problem: 10+9a{ mod } 23 =14.I know that a=3, but I don't know the steps to apply to these digits to get 'a' if I were to calculate it. 10+9*3{ mod }23=14. I'm just looking for the steps on how to…
0
votes
1 answer

Tips to find the minimum period of an exponential congruence

I have to find the minimum period of this congruence: $2^x \equiv 8\;(11)$ $$ 2^1 \equiv2,\;2^2 \equiv4,\;2^3 \equiv8,\;2^4 \equiv5,\;2^5 \equiv-1,\; 2^{10} \equiv1 $$ My question is: how do I know that it is not necessary to calculate the…
Shyvert
  • 177
0
votes
1 answer

Find the remainder when 5^23 + 4^6 is divided by 10

How would I go about solving this using modular arithmetic?
Zey
  • 1