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

How to prove the modular multiplication property?

In Number Theory, I have seen many a times the following property being used though I don't know what it's called formally (that makes it harder to Google): (a * b) (mod n) = (a mod n) * (b mod n) What is this called and how can it be formally…
sherlock
  • 191
1
vote
3 answers

Prove the polynomial $f(x) = 3x^3+x^2+2x+1155$ has no root in $\mathbb{Z}$

Prove the polynomial $f(x) = 3x^3+x^2+2x+1155$ has no root in $\mathbb{Z}$ The hint says If $f$ has a root in $\mathbb{Z}$, then $f$ has also a root in $\mathbb{Z}/2\mathbb{Z}$. I'm still confused
Alicia
  • 47
  • 4
1
vote
2 answers

If you get the remainder of two numbers, add the remainder to the larger number, and repeat the process, will there eventually be no remainder?

In other words, $$\forall n,s\in\mathbb{N}, n\geq s$$ $$\begin{align}n\bmod{s}&=m_1\\(n+m_1)\bmod{s}&=m_2\\(n+m_2)\bmod{s}&=m_3\\\vdots\\(n+m_a)\bmod{s}&=0\end{align}$$ Is that guaranteed? I've only run a simple program and it seems it holds for…
1
vote
6 answers

Finding the last two digits of $17^{198}$

Question 1: What are the last two digits of $17^{198}$? My Attempt: The pdf hinted to reduce it via mod $100$. So my work is as follows: Since $17^2\equiv289\equiv-11\mod100$, we have$$17^{198}\equiv (-11)^{99}\equiv-11^{99}\mod100$$ However, I'm…
Crescendo
  • 4,089
1
vote
1 answer

Is $2\Bbb Z_4$ a summand of $\Bbb Z_4$?

I figured the answer would be no since there are no submods of $\Bbb Z_4$ that do not intersect with $2\Bbb Z_4$, but I am not sure.
Mark
  • 65
1
vote
1 answer

One variable modulo equation

I was attempting Wiener's Attack on RSA with a simple example and I came to a one variable modulo equation which I managed to solve with brute-force but I think it must be easier than that with some algorithm/formula. here it is. $e * d \equiv 1…
Leonardo
  • 557
1
vote
0 answers

modulo of perfect squares

Suppose I have a number $k$ such that $k < p$ but $k^2 > p$ Now I need to find smallest possible value of n such that $n^2 \bmod p\equiv k^2 \bmod p$ I found a pattern $k^2 \bmod p \equiv (p - k)^2 \bmod p$. Is there any other method? Are there…
BEC
  • 13
1
vote
2 answers

Compute sqrt(5) in Z_11 with Fermat's little theorem

I am trying to solve this. If I am correct, applying Fermat's little theorem here gives: $\sqrt{5}^{10} \equiv 1 \pmod{11}$ $\sqrt{5}^{10} = 5^5 \equiv 1 \pmod{11}$ $5^{2} \equiv 3 \pmod{11}$ $5^{3} \equiv 5*5^2 \equiv 3*5 \equiv 4 \pmod{11}$…
Leonardo
  • 557
1
vote
3 answers

Modular arithmetic congruence class simple proof

I have the following question but I'm unsure of how it can be approached by a method of proof. I'm new to modular arithmetic and any information on how to solve this would be great for me. (b) Let $t,s\in\{0,1,2,3,4,5\}$. In $\mathbb Z_{25}$, prove…
1
vote
4 answers

Modular Arithmetic order of operations

In an assignment, I am given $E_K(M) = M + K \pmod {26}$. This formula is to be applied twice in a formal proof, so that we have $E_a(E_b(M)) =\ ...$. What I'm wondering is; is the original given formula equal to $(M + K)\pmod{26}$, or $M + (K…
Cat
  • 113
1
vote
3 answers

Prove that $n = i^2 - j^2 \iff n \neq 2 \mod4$ hints

I'm trying to prove that $n = i^2 - j^2 \iff n \neq 2 \mod4$ for all integers n, I'm running into issues getting much traction on this. I know that $n \neq 2 \mod4$ can just be split up into each case but I can't really get anywhere with that. Any…
Cjen1
  • 259
1
vote
2 answers

Computing large modulus by hand

I am having trouble computing $12^{15}$ mod $2016$ due to the large size of the modulus. I need to do this and list the steps out by hand
John
  • 13
1
vote
2 answers

Modular Arithmetic on Circle

On the unit circle, what does the set $\left \{ n \bmod{2\pi}:n \in \mathbb{N}\right \}$ represent? What is the subsequentieal limits of $\left \{ \sin(n) \right \}_{n\in \mathbb{N}}$? I am probably really off. But I am thinking that every number…
Lemon
  • 12,664
1
vote
1 answer

Solution $x^{73}+x^{48}+x^{26} \equiv 0$ mod $13$

I am trying to solve $x^{73}+x^{48}+x^{26} \equiv 0$ mod $13$. Can I say that By Fermat’s Little Theorem I have $x^{12} \equiv 1$ mod $13$? If I am correct remaining part will be simple but otherwise I have no idea how to deal with it.
Okumo
  • 313
1
vote
2 answers

Proving identities (mod $pq$) using Fermat's little theorem?

I have come across this question, which reminded me of Fermats little theorem, i dont know if the Fermats theorem is actually in use in the following mathematical statements an integer a is a coprime with p and a coprime with q (p and q are…