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

Modulo arithmetic: finding "c" when there is a number attached to it

I am fairly new to number systems and notations. I have a problem where I need to find $c$ in: $13c ≡ 27a − b^{3} \mod (43)$ given that $0 \leq c < 43$. Also, $a ≡ 27 \mod(43)$ and $b ≡ 19 (\mod 43)$ where $a$ and $b$ are integers. I know that the…
0
votes
1 answer

If $p\equiv 1 \mod 4$ then $|k_i - k_j|=\frac{p-1}{4}$

The Title basically says it already. Maybe this is simple, but I don't see it yet. If $p\equiv 1 \mod 4$ is a prime, then for every $i\equiv g^{k_i} \mod p$ with $i\in \{1,2,...,\frac{p-1}{2}\}$, where $g$ is a generator of $\mathbb{Z}_p$, there…
Diger
  • 6,197
0
votes
2 answers

How to show that $5^{2m} ≡ 2^{2m} \mod 7$ , but not $5^{2m} ≡ -2^{2m} \mod 7$

I am not quite sure how to show that $5^{2m} ≡ 2^{2m} \bmod 7$ , but not $5^{2m} ≡ -2^{2m} \bmod 7$ My answers always show that $5^{2m} ≡ -2^{2m} \bmod 7$ , however, when I denote m with an actual number, it never works.
user824576
0
votes
2 answers

How to interpret the question: "How many elements from the set $\mathbb{Z}/42\mathbb{Z}$ satisfy $x^2=x$?"

I simply don't understand the question. Doesn't $\mathbb{Z}/42\mathbb{Z}$ consist of $42$ subsets? (Namely $\{0,42,84,\cdots\}, \{1,43,85,\cdots\}, \cdots, \{41, 83, 125, \cdots\}$) And then how would you square an entire subset? New to this website…
0
votes
1 answer

Prove or Disprove: $a \equiv b \bmod m$ iff $a^3 \equiv b^3 \bmod m$?

Prove or Disprove: $a \equiv b \mod m$ iff $a^3 \equiv b^3 \mod m$? I'm trying to determine if this is true or not. I have already proved this going one way. I know that if $a \equiv b \mod m$ then $a^3 \equiv b^3 \mod m$. How should I start the…
complexanalysis
  • 533
  • 2
  • 12
0
votes
1 answer

Modular Inverting

I was solving a problem Called Modular inverting on Crypto Hack the problem states that: if we have 3 * d ≡ 1 mod 13 how can we get d using Fermat Little Theorem I solved it using basic math but I found a solution that I couldn't…
0
votes
0 answers

Does $(X-Y) \bmod Z \neq 0$ imply that $X \bmod Z \neq Y$ if (X-Y)>Z>Y? ($X,Y,Z \in \mathbb{N}$)

Does $(X-Y) \bmod Z \neq 0$ imply that $X \bmod Z \neq Y$ if (X-Y)>Z>Y? ($X,Y,Z \in \mathbb{N}$) I'm not sure how to prove/disprove this. I tried using the fact that $(A + B) \bmod C = (A \bmod C + B \bmod C) \bmod C$ or writing this as $X-Y \neq…
Dawid
  • 51
0
votes
1 answer

Find $B$ that satisfy $B^2 \equiv N \pmod b$ and $B \equiv 0 \pmod c$

How to construct an integer $B$ that has the property of $B^2 \equiv N \pmod b$ and $B \equiv 0 \pmod c$, where $c$ belongs to a group of small prime numbers of the size $s$ and $b$ is a prime number outside that group. I need to solve this in order…
Ilya Gazman
  • 1,440
0
votes
2 answers

$(3*5)*(5*9)$ modulo arithmetic $12$

Modulo $12$ multiplication table and I got $3$, but I don't know if it's true or not. I don't know whether it's correct place. Please reopen it.
0
votes
1 answer

Exponential laws in modular arithmetic | disappearing mod N

Why is $(g^b \bmod N)^a \bmod N = g^{a*b} \bmod N$ ? Specifically: Why/how does the mod N in the round brackets disappear from the first expression $(g^b \bmod N)^a \bmod N$? I know of the exponential law that $g(^a)^b$ is equal to $g^{a*b}$ but I…
0
votes
2 answers

Modular arithmetic question.

What solutions does the equation $4x≡2\mod 10$ have? (Hint, it will have more that one.) What about solutions to an equation $ax≡d \mod n$, where $d=\gcd(a,n)$? This is the question that appear in our universities last year paper. But it is seems…
0
votes
1 answer

What solutions does the equation 4x≡2mod10 have? (Hint, it will have more that one.) What about solutions to an equation ax≡dmodn, where d=gcd(a,n)?

What solutions does the equation $4x\equiv2\mod10$ have? (Hint, it will have more that one.) What about solutions to an equation $ax\equiv d\mod n$, where $d=\gcd(a,n)$? This is the question that appeared in our universities last year paper. But…
0
votes
1 answer

Any easier way to get the quotient and remainder from a minus number divided by a positive one?

negative number divided by positive number, what would be remainder? I've read these answers linked above, but I don't feel I'm answered enough. $$-27 = \underbrace{-6}_q\cdot \underbrace{5}_d + \underbrace{3}_r$$ They say this, but I don't think I…
0
votes
2 answers

Why when $t\equiv n\pmod s$, $n$ is also $t - s\lfloor \frac{t}{s}\rfloor$?

I'd like to know why when $t\equiv n\pmod s$, $n$ is also $t - s\lfloor \frac{t}{s}\rfloor$? Here, $n\in[0;s[$ I can't find a way to prove $n$. Thank you for your help!
0
votes
2 answers

Why are check digits for UPCs computed modulo 10, whereas for ISBNs, modulo 11?

Recently I was reading a mathematics book and encounterd the fact that UPC codes have a check digit at the end that is computed modulo 10, whereas ISBN numbers have a check digit that is computed modulo 11. What disturbs me is the fact that why is…
coderboy
  • 113