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

How do we find all possible values of $a$?

$$2a5b \equiv 0 \mod 15$$ How do we find all possible values of $a$? Here I tried to divide both sides by 2 and 5 respectively $$ab \equiv 0 \mod 15 \implies a \in \{3,6\}, b \in \{0\}$$ However, I think the way I used is so meaningless since this…
Melz
  • 792
0
votes
1 answer

Find all integers $x,y$ whose squares sum up to $c$ mod 5

Find all integers $x,y$ such that $x^2 + y^2 \equiv c \pmod{5}$. I managed to solve by trying one-by-one, but I guess there is some other way to solve this?
0
votes
2 answers

How to reduce the congruence $(p-1)^{p-1}\equiv 2^{p-1}\pmod{p^2}$ into $p(p-1)+2^{p-1}-1\equiv 0\pmod{p^2}$?

In addition, how is $(p-a)^{p-1}-a^{p-1}\equiv -(p-1)pa^{p-2}\pmod{p^2}$ derived by binomial theorem?
0
votes
0 answers

Splitting the mod value

I have $a^x \bmod M$ and I am running algorithm based on $$ (a^2)\bmod M = (a\bmod M) * (a\bmod M) \bmod M.$$ The problem is that if $M$ is longer than half of digits of long long int (for example 14 digits long when long long int is max 19 digits),…
eXPRESS
  • 203
0
votes
3 answers

Prime number and divisibility

Let $p$ be prime, prove that for any integer $r$, there at most $2$ solutions to the equation $x^2-r \equiv 0\pmod p$. I don't understand the question as if $p=2$, and $r$ odd, then $x^2$ will need to be odd, and we have an infinite number of…
0
votes
4 answers

Find all ordered pairs $(a,b)$ of positive integers for which $\frac{1}{a} + \frac{1}{b} = \frac{3}{2018}$

This question comes from the 2018 Putnam and can be found in the following link: https://kskedlaya.org/putnam-archive/ So far, I got the following two equations using simple algebra: (1) $2018a = b(3a - 2018)$ (2) $2018b = a(3b - 2018)$ Then, I…
Skm
  • 2,296
0
votes
0 answers

$13t$ mod $5.2=5.2-26t$ mod $5.2$. Solve for $t$

Two points are 5.2Km apart. Two people are initially at the opposite ends. They start running between the points back and forth with speeds of 13Kmph and 26Kmph respectively. They do this for 6 hours. How many times do they meet each other? My…
Ryder Rude
  • 1,417
0
votes
1 answer

For what values of t, $20t\equiv15t \pmod {0.5}$?

The question is: There is a race on a circular track of length $0.5$ km. The race is $4$ km. Two people start at the same point with speeds $20$ m/s and $10$ m/s respectively. Find the distance covered by the first person when they meet the second…
Ryder Rude
  • 1,417
0
votes
4 answers

Solve for $m$: $m^5 + 7m + 8 \equiv 0 \pmod 3$

I got about this far: $$m^5 + 7m \equiv -8 \equiv 1 \pmod 3$$ I'd have a much easier time solving a linear equation, but I have no clue about this one. $$m(m^4 + 7) \equiv 1 \pmod 3$$ m itself is not divisible by three, but we already knew that...…
Minah
  • 53
0
votes
0 answers

How can I check if "value is fractional multiple of another" in "modulo sense"?

How can I check if "value is fractional multiple of another" in "modulo sense"? Typically in programming the modulo is used like: if n mod m == 0 which means that $n$ is an integer multiple of $m$. However, what if I want to check whether $n$ is a…
mavavilj
  • 7,270
0
votes
0 answers

solving congruence $a^{6p−6} \equiv 1 \pmod{9p}$

Let $p$ be a positive prime number different from $3$ and $a$ be an integer not divisible neither by $3$ nor by $p$. Show that in this case $a^{6p−6} \equiv 1 \pmod{9p}$
Y.xin
  • 57
0
votes
2 answers

Multiplication and modulo - Order of operations

Simple question I have $$a\cdot b\cdot c\;mod\;p$$ How do I interpret this? Do i read it as this $$(abc)\;mod\;p$$ or is it $$a\cdot b\cdot (c\;mod\;p)$$ Or do I completely misunderstand modular arithmetic? Thanks!
0
votes
2 answers

Prove $4|n$ if and only if $4|(10a_1+a_0)$

Prove $4|n$ if and only if $4|(10a_1+a_0)$. I know there may be "duplicates" out there, but most of them are for the case of $3|n$ and stuff like that. I'm still confused as to how the thought process works though. I have to prove the statement for…
Claire
  • 167
0
votes
1 answer

Modulo Arithmetic equations

How to find the value of the unknown in the equations . I have tried finding the value y by equating the left hand side to the right hand side $\;20\pmod 9 = y\pmod6$, find the value of $y$
Mickey
  • 1
0
votes
2 answers

modular arithmetic addition rule

Consider this addition rule in modular arithmetic: If I take n=10, a=3, b=7 Then, on the left hand side, we have (3)mod10 + (7)mod10= 3 + 7 = 10 On the right hand side, we have 10 mod10, which is zero. LHS is therefore not equal to RHS. What am I…