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
2
votes
2 answers

Reducing modulo equations

How do I reduce the following and remove the $11$ from LHS, $$ 11x \equiv 4 \ \ \text{mod }50 $$
2
votes
0 answers

Unique solution to 2 congruence equations

Let $p$ be a prime, and $x,n$ be integers with $n\geq1$ I am trying to show that the equations $y \equiv x {\mod{p}} $, and $y^p \equiv y {\mod{p^n}}$ have a unique solution for $y$ in $\mathbb{Z}_{p^n}$. I have found a solution $y \equiv…
VACT-1729
  • 344
2
votes
3 answers

Solving a congruence system (which has other solutions)

I am trying to solve this congruence system : $$\begin{cases} 3x+7y\equiv 5[11]\\ 8x+4y\equiv6[11] \end{cases} $$ I multiply first by $8$ and $3$ both equations resp. $$\begin{cases} 24x+56y\equiv40[11]\equiv7 [11]\\ 24x+12y\equiv18[11]\equiv7…
BrianTag
  • 1,395
  • 7
  • 18
2
votes
2 answers

Find the smallest possible integer that satisfies both modular equations

Find the smallest positive integer that satisfies both. x ≡ 4 (mod 9) and x ≡ 7 (mod 8) Explain how you calculated this answer. I am taking a math for teachers course in university, so I'm worried about guessing too much in fear that I will teach…
Shayna
  • 137
2
votes
2 answers

Understanding the answers of $x^2 \equiv 28 \pmod 6$

Solving $x^2 \equiv 28 \pmod 6$ The answers are: $x \equiv 2 \pmod 6$ and $x \equiv 4 \pmod 6$. When I plugged in to check the answers, it would be $2^2 \equiv 4 \pmod 6$ and $4^2 \equiv 16 \equiv 4 \pmod 6$. It is $4$ but not $28$, why is this,…
user870290
2
votes
1 answer

Determine the remainder when

$1025^{1005}\equiv x(1023)$ I did: $1025\equiv 2(1023)$ $1025^{1005}\equiv 2^{1005}(1023)$ I don't know the next step.
Y.xin
  • 57
2
votes
1 answer

Introduction to modular arithmetic (residues)

I have been recently using the book introduction to Number Theory from Art of Problem Solving as I am preparing for the upcoming AMC 10 (I'm an 8th grader). In section 12.3 problem 12.3.3 it says Determine the residue of each of the following within…
QuantumPi
  • 323
2
votes
2 answers

How to prove that the remainder of $15^{2098}$ divided by $14$ is $1$?

I have to compute the remainder of $15^{2098}$ divided by $14$, I know that the answer will be $1$ because $15$ is $14+1$ and the remainder of every $15$'s power will be $1$ when divided by $14$, the problem is that I can't write that as answer…
Ivan.2j
  • 53
  • 3
2
votes
3 answers

5x ≡ 3 (mod 12) how do you find the first three xs without listing them?

5x ≡ 3 (mod 12). The question asked me to find the smallest positive non zero integers that can be plugged in the place of x. I only know how to find the answer by making a list. 5, 10, 3, 8, 1, 6, 11, 4, 9, 2, 7, 0, 5, 10, 3. It took 12 for 3 to…
2
votes
2 answers

Show that $7^{(2n^2 + 2n)}$ is congruent to $1 \bmod 60$

Just finished an exam but I couldn't solve the following task: Show that following holds true for all $n \in \mathbb{N}$: $7^{2(n^2 +n)} \equiv 1 \mod 60$ I've tried to show that the exponent is a multiple of $\varphi(60) = 16$ and then use…
Algebruh
  • 600
2
votes
0 answers

How many modular inverse number pairs between $0$ and $n$?

How many positive a,b pair solutions are there for the formula below and is there an easy way to find them all? $$a * b \equiv 1 \pmod{n}$$ Where $a,b,n \in \mathbb{Z}$ and $0 < a \leq b < n$
Ilya Gazman
  • 1,440
2
votes
1 answer

There are only two six-digit integers $N$, each greater than $100,000$. for which $N^2$ has $N$ as its final six digits

There are only two six-digit integers $N$, each greater than 100,000 for which $N^2$ has $N$ as its final six digits (or $N^2-N$ is divisible by $10^6$). What are these two numbers? Is the problem solvable by the Chinese Remainder Theorem? If so,…
2
votes
2 answers

Modular calculation high exponent?

I want to show, that $5^{96}\equiv -1 \pmod{193}$, without using the formula for quadratic residue. So far I have : $5^{96}\equiv 5^{4\cdot24} \equiv 625^{24}\equiv 46^{24}\equiv 186^{12}\equiv -7^{12}\equiv 7^{12}\equiv 7^{3\cdot4}\equiv…
2
votes
0 answers

Last 2 digits of modular exponentiation

Is there any shortcut way to find the last two decimal digits of a modular exponentiation (base always is a single digit number) without doing square and multiply? As an example in $$2^{100001} \pmod{10001}$$ the last two decimal digits are 48.
Mohsen Afshin
  • 463
  • 4
  • 15
2
votes
3 answers

Congruence Problem

Given $a,m \in\mathbb{N}$ with $gcd(a,m)=1$, let $x_1\in\mathbb{N}$ be a solution to the congruence $ax\equiv1\pmod m$. For each integer $k\ge1$, number is defined as $x_k:=\frac{1}{a}(1-(1-ax_1)^k]$. Prove that $x_k$ is a solution to the congruence…
Bryan
  • 725