Mathematics Stack Exchange
Mathematics Stack Exchange

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

Prove if $n \equiv 2 \pmod 7$, then $7 \mid (n^2 + 10)$

Prove if $n \equiv 2 \pmod 7$, then $7 \mid (n^2 + 10)$. I tried saying since $n \equiv 2 \pmod 7$, then $7 \mid n - 2$. Thus $7 \mid -5( n - 2)$ or $7 \mid -5n + 10$ and $-5n \equiv 10 \pmod 7$. Since $n^2 \equiv 10 \pmod 7$, then $7 \mid n^2 +…
Pasie15
  • 491
0
votes
1 answer

Fundamental theorem of algebra in modular arithmetic

suppose you have a polynomial $P(x) = a_0+a_1x+...+a_kx^k$. How can you prove that at most $k$ numbers satisfy $P(x) \equiv 1 \mod n$ ? To me this looks like the fundamental theorem of algebra, however, in modular arithmetic. Yet, I don't see why…
Max
  • 1
  • 1
0
votes
3 answers

Find all solutions for modulo equation

Given $(133x \equiv 107) \pmod{91} , x \in N $ My first attempt was to do: $133x - 91z \equiv 16 \pmod{91}$ $133x - (91z + 16) \equiv 0 \pmod{91}$ $133x - 16 \equiv 0 \pmod{91}$ From there on I do not know how to continue. Am I on the write way?
Peter
  • 35
0
votes
2 answers

Let $p$ be a prime number such that $p \equiv 3 \pmod 4$. Show that $x^2 \equiv -1 \pmod p$ has no solutions.

Let $p$ be a prime number such that $p \equiv 3 \pmod 4$. Show that $x^2 \equiv -1 \pmod p$ has no solutions. I noticed that this is equivalent to proving $x^2\equiv 2(2k+1) \pmod p$. I also know that $x^2 \neq 2(2k+1)$. But I still can't prove…
King Ghidorah
  • 607
0
votes
1 answer

Define the relation $\sim$on $\mathbb{Z}$ by $a \sim b$ if and only if $5a \equiv 2b \pmod{3}$

Define the relation $\sim$ on $\mathbb{Z}$ by $a \sim b$ if and only if $5a \equiv 2b \pmod{3}$. Prove that $\sim$ is an equivalence relation on $\mathbb{Z}$. Identify the distinct equivalence classes on $\mathbb{Z}/\sim$. How can I prove something…
Bradley Barrows
  • 263
0
votes
2 answers

Why does $y^{pq} ≡ y $[mod $pq$] imply $y^{pq} ≡ y [$mod $p$] and $y^{pq} ≡ y [$mod $q$]? $p, q$ prime.

Why does $y^{pq} ≡ y $[mod $pq$] imply $y^{pq} ≡ y [$mod $p$] and $y^{pq} ≡ y [$mod $q$]? where $p, q$ prime. I can't see it from re-writing it as $y^{pq} = y + kpq$ for some integer $k$, as you cannot then divide by p or q. Instead, re-writing…
timni
  • 75
0
votes
1 answer

Multiplication and Subtraction in Modular Arithmetic

How would I determine whether $a^2-3b^2=0 \pmod 7$? By trying all values of $a$ and $b$ it is clear that this is only true for $a=b=0$, but I need a way to show this algebraically so that I can generalize to different values for 3 and 7.
Aaron Dufour
  • 157
0
votes
1 answer

Floor function inequality: $\frac{n^2}{x}-\left\lfloor\frac{n^2}{x}\right\rfloor+\frac{2n+1}{x}-\left\lfloor\frac{2n+1}{x}\right\rfloor<1$

I would like to dissect the following inequality to figure out its properties. $$\frac{n^2}{x}-\left\lfloor\frac{n^2}{x}\right\rfloor+\frac{2n+1}{x}-\left\lfloor\frac{2n+1}{x}\right\rfloor>1$$ where $n>0$ and $0
user122523
  • 357
0
votes
2 answers

How to divide $2x \equiv 4 \pmod {7}$ to get just $x \equiv \Box \pmod{7}$

I've got three simultaneous congruence to solve, which I now know how to do, but in this particular question, one of them is in the form of $2x \equiv$ instead of of $x \equiv$ that I'm used to: $$\begin{align*} x &\equiv 2 \pmod 3\\ 2x &\equiv 4…
Arvin
  • 1,733
0
votes
2 answers

In modular arithmetic is $m^{1/x}$ =! $(m^x)^{-1}$

In modular arithmetic is $m^{1/x}$ =! $(m^x)^{-1}$ as we always use inverse instead of reverse in multiplicative group.why reverse operation is not used in modular arithmetic and if one want to use reverse how to solve reverse.
Aria
  • 291
0
votes
3 answers

unique solution for mod equation

If I have these equations $a\equiv b \pmod c$ $d\equiv e \pmod c$ All known except $c$ and $\gcd(b−a,e−d)=1$ how do I find the unique solution for $c$? and if the gcd!= 1 how do I find some possible solutions?
user1510863
  • 361
0
votes
3 answers

Define a relation on $Z$ by a~b if and only if $a=b(mod2)$ and $a=b(mod5)$. Show that ~ is an equivalence relation.

The if and only if is throwing me off. Would the first direction be to prove the two modular conditions hold if the relation is an equivalence relation? Furthermore, I'm having difficulty proving reflexivity, symmetry and transitivity with the…
user122661
  • 983
0
votes
1 answer

What day of the week was it on this date in the year 1000?

Don't forget that every year divisible by 4 is a leap year, except that century years are only leap years if divisible by 400 (e.g., 2000 was a leap year, but 1900 was not). Another question in my homework.. not really sure how to go about solving…
user122661
  • 983
0
votes
1 answer

Solving for modular expression?

I stuck somehow on repetition old math exercises...could someone explain the following expression: $(n!-1)$ mod $ n $ Thanx
Jacky
  • 87
1 2 3
…
99 100