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

Modular congruency application

I want to use modular congruences to show that $5=3x^2-4y$ has no solutions on $(x,y)\in\mathbb Z^2$. Here's my attempt: Take $3x^2\equiv_5 4y$. Then since $2$ is an inverse modulo $5$, $x^2\equiv_58y\equiv_53y$. Hence, $$x^4\equiv_5 4y^2$$ By…
Lex_i
  • 2,072
  • 10
  • 26
0
votes
1 answer

Divison in modular arithmetic

I have just read that 3x congruent to 12 modulo 15 is equivalent to x congruent to 4 modulo 5. However, I thought division could only be done in modular equations if gcd(a,n)=1 but in this case, gcd(3,15)=3. Could someone please explain to me why…
John
  • 29
0
votes
4 answers

How to compute $x^7 \equiv 1 \pmod{29}$?

I mean, can someone show me the general approach to solve exercises like this one? I've seen here that many questions related to this were asked but no one showed the step by step approach. Thank you
Osmion
  • 9
  • 1
0
votes
1 answer

A weird modular identity

I came up with the following modular identity which looks a bit weird but can be checked numerically for (almost) arbitrary choices of $n$ and $N > n$ when $N = k\,n + r$ with $r < n$. We have $k = \lfloor N/n \rfloor$ and $r = N\%n$. My claim is…
0
votes
0 answers

Prove that a ≡ b (mod n) if and only if a and b leave the same remainder when divided by n

I want to show that , in a given pair, there exists a pair where $x-y \equiv 0 \pmod n$ and in order to do that I can write an algorithm that looks for two different instances where we have the same remainder in $\pmod n$. So that we would have $0…
nich
  • 1
0
votes
0 answers

Trial multiplication stop condition for discrete logarithm

I wrote a very simple algorithm to find the discrete logarithm of a certain number, it simply starts at p=1 and increments it until it finds a value of p that satisfies (b^p) % m = x. The problem I have is that while this algorithm works when there…
Pop Flamingo
  • 807
  • 1
  • 8
  • 17
0
votes
0 answers

Fast modular calculation

Pow(x,2)=13 (mod N) For figuring out the x value in huge numbers N, any fastest method? N is a square number and the range 1
0
votes
0 answers

Generally is floor(x) or mod(x,y) (modulo function) used more in maths?

I know these functions are interrelated cause $mod(x,1)+floor(x)= x$ And I think they're pretty cool functions but I don't see them used much at all in maths. I guess mod is used in number theory but i never see it anywhere else. So I asked this…
0
votes
1 answer

Can I prove bounds on this modular equation...

Hypothesis: $\forall$ odd $n > 1$, $\exists\ m
aSteve
  • 147
0
votes
3 answers

Easier way to compute the solution to a modular equation system

Using the extended euclidian algorithm and the Chinese remainder theorem, I am able to find a solution to the following equation system: \begin{align*} x \equiv 4 \bmod 39\\ x \equiv 5 \bmod 70 \end{align*} The issue I have is that while I am able…
Pop Flamingo
  • 807
  • 1
  • 8
  • 17
0
votes
0 answers

What does the highlighted expression mean

What does the highlighted expression mean Looks like E is a function with arguement M. Let M be 00. Hence, E(00) equals to plaintext letter A. But how can the following expression can be true: A ≡ 3 (modulo 26) ? Can you please explain that?
0
votes
1 answer

System of equations ( Modulo )

Hello everyone. I solved this system, but I dont know how to collect the answers. So I got: (x_1 -x_2 -x_3 = 0) (0 -2x_2 0 = 0) (0 0 x_3 = 0) in matrix. x_3=x_2=x_1 = 0 I got. But there is one solution. x_1 = x_3 = 1. x_2=0. But how can I…
0
votes
2 answers

Show that there is no complete set of representatives for $\mathbb Z/71\mathbb Z$ that includes two of the numbers 1066, 1492, and 1776.

Show that there is no complete set of representatives for $\mathbb Z/71\mathbb Z$ that includes two of the numbers $1066, 1492$, and $1776$. My plan is to add the first two representatives of the set [Z=x] and follow through with a basic proof. but…
billy
  • 151
0
votes
0 answers

What is the proof for the naive method of modular inverse?

I was reading on a website that in order to find a multiplicative inverse you just have to multiply the number you are given by $1\ldots n-1$ where $n$ is the modulus and you guaranteed to find the multiplicative inverse. For example if you have,…
Neel Sandell
  • 306
  • 1
  • 10
0
votes
3 answers

Having difficulty in understanding addition in modular arithmetic

I am trying to understand modular arithmetic using the article posted on Brilliant.org. Howeverver, I am having trouble understanding the first addition property when applied to the following examples: $$\text{Property 1: If }\;a+b=c\text{, then…