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
4
votes
1 answer

Solutions to the equation $x^y \equiv y^x$ in $\mathbb Z / p \mathbb Z$, $p$ prime.

I am looking for the number of integer solutions $(x, y)$ to the equation $$x^y \equiv y^x \mod p, \qquad 0 < x, y < p,$$ where $p$ is a prime number. However, even for small prime, I am having trouble finding all solutions. In general, I know that…
byhill
  • 75
4
votes
6 answers

How to find remainder modulo $n$, when $n$ is a large number

I am doing RSA questions and I really could use help! Can someone show me a simple way to find $25^9 \pmod{33}$?
4
votes
1 answer

Why does this "trick" for taking the modulus of a number work?

I was recently looking up solutions to taking the modulus of a very large number ($\sim22$ digits). Because computers can't handle this operation on such large numbers I went looking and found a novel solution to taking a number's modulus in…
4
votes
1 answer

Finding N modulo 36, given modulo 2, 3, 4, 9

Let N be the integer of putting all natural numbers from 1 to 35 together Therefore, N = 1234567891011121314...35 Find the remainder when N is divided by 36 Here's what I have done: $$N\equiv1(\textrm{mod}\ 2)$$ $$N\equiv0(\textrm{mod}\…
Cyh1368
  • 839
4
votes
5 answers

Better method to solve $x^2-x-1=0$ modulo $11$

I want to solve $x^2-x-1=0$ modulo $11$. I already know that the solutions are $x=4$ modulo $11$ and $x=8$ modulo $11$, but I got this result by trying. I also know that I can get these solutions by using the usual quadratic formula and doing some…
kubo
  • 1,918
4
votes
4 answers

Find a number $b$ such that $a\cdot b\equiv 1\mod m$

Given two integers $a$ and $m$, such that $a\mathop\bot m,$ how can I find an integer $b$ such that $a\cdot b\equiv 1\mod m?$
FUZxxl
  • 9,307
4
votes
3 answers

Proof of intersection of two positive integer congruence classes

I am reviewing the foundation course I took in year 1 while a question caught my eyes: Let A be the congruence class of 1 mod 3, and B the congruence class of -1 mod 4. Prove that A∩B is a congruence class mod 12. The answer is simple, 7 mod…
4
votes
1 answer

Meaning of congruence (in twin prime criterion)

I'm a programmer, a newbie on math. I'm trying to code to list twin prime. I've found this: $(m, m+2)$ is twin prime, iff $4((m-1)! + 1) \equiv -m \pmod {m(m+2)}$ The pair (m, m + 2) is twin prime, iff 4((m − 1)! + 1) ≡ −m (mod m(m + 2)). However,…
Yves
  • 151
4
votes
2 answers

find the sum of the series with given first two terms.

We are given $2$ integers, $a,b$ such that $0\leq\,a$ and $b\leq9)$, that are the first $2$ elements of a series. Each consecutive term of the series is defined as the sum of all the previous elements of the series, modulo $10$. That is, the first…
4
votes
2 answers

Modular equations system

I have the following task - I have to find all a for which the following system has a solution: $x \equiv 1\pmod 2$ $x \equiv 2\pmod 3$ $x \equiv a\pmod 5$ I will be very grateful if someone show me the principle behind solving this. By the way, I…
4
votes
2 answers

Why does $n \equiv n^{21}\bmod 33$?

I’m trying to understand why $n \equiv n^{21} \bmod 33$ for $n \in \{0, \ldots, 16\}$. I know that $\phi(33)=20$ and so $n^{20} \equiv 1 \bmod 33$ for all $n \in \mathbb Z$ coprime to $33$. This then simply gives $n^{21} \equiv n \bmod 33$ for the…
4
votes
2 answers

Solving for a variable in a modular arithmetic equation

$\fbox{$13x + 1 \equiv 0 \pmod {100}$}$ I solved the equation above by trying different multiples to isolate $x$ until I found something that worked. I have two questions: $\fbox{$1.$}\ $ What if there was no solution for $x$? How would I be able…
Dan
  • 49
4
votes
2 answers

Bijection from modular multiplication?

Say we have two integers $n$ and $k$, such that $0 < k < n$ and $gcd(n, k) = 1$. Why is it that if we take every integer $x\in\{0,\dots, n-1\}$ and compute $k\cdot x \ (mod \ n)$, we get as remainders all numbers from $0$ to $n-1$, with no…
4
votes
5 answers

What is $26^{32}\bmod 12$?

What is the correct answer to this expression: $26^{32} \pmod {12}$ When I tried in Wolfram Alpha the answer is $4$, this is also my answer using Fermat's little theorem, but in a calculator the answer is different, $0.$
4
votes
1 answer

What does "unique modulo" mean?

"The square root of a square number modulo 257 is unique modulo 257" (This is something that I have to prove or invalidate) I don't understand what 'is unique modulo 257' means?
user599763