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

Find the remainder when $13^{13}$ is divided by $25$.

Find the remainder when $13^{13}$ is divided by $25$. Here is my attempt, which I think is too tedious: Since $13^{2} \equiv 19 (\text{mod} \ 25),$ we have $13^{4} \equiv 19^{2} \equiv 11 (\text{mod} \ 25)$ and $13^{8} \equiv 121 \equiv 21…
1
vote
3 answers

Exponential Modular Arithmetic Calculation

How to calculate $32^{61} \bmod 85$ by hand ? 85 = 5 * 17 can anyone show me the steps in detail ?
1
vote
1 answer

How to efficiently find the modulus of a product of lots of integers?

Let us have about 100 or so random integers such as: $$ A_1 = 1234123\\ A_2 = 13713\\ A_3 = 41232\\ A_4 = 123\\ ...$$ Now I want to find an efficient way to get the modulus $(A_1 \times A_2 \times A_3 ..... \times A_n ) \mod B$ where B is an integer…
zooby
  • 4,343
1
vote
2 answers

Fermat's Little Theorem Transformation

I am reading a document which states: By Fermat's Little Theorem, $a^{p-1}\bmod p = 1$. Therefore, $a^{b^c}\bmod p = a^{b^c\bmod (p - 1)} \bmod p$ For the life of me, I cannot figure out the logic of that conclusion. Would someone mind explaining…
Plastech
  • 121
1
vote
2 answers

Determine the remainder of $A \cdot B$ and $A+B$.

$$A \equiv 3 \pmod{5}$$ $$B \equiv 4 \pmod{5}$$ Determine the remainder of $A \cdot B$ and $A+B$. Rewriting the equations $$A-3 \equiv 0 \pmod{5}$$ $$B -4 \equiv 0 \pmod{5}$$ Which yields $A \in \{3,8\}$ and $B \in \{4,9\}$. As it appears, I've…
Busi
  • 572
1
vote
2 answers

How to reduce a polynomial congruences

Consider the Legendre Symbol (2|p) which give the congruences $2^{\frac{p-1}{2}} = (-1)^{\frac{p^2-1}{8}} mod p$. Now ${\frac{p^2-1}{8}}$ is odd if is equal to 2k+1 with k integer that gives $p^2 = 16 k + 9$ and brings to the polynomial…
user135617
1
vote
1 answer

Unknown Exponent In Modular Equation

If $(9^{4})^{x} \equiv 12 \pmod{23}$, then how do I find $x$? I have tried solving this, but I was thinking if there is a step by step formula. I know that any number from the group order may suffice. Will I still be able to find $x$ when the…
DENN
  • 11
1
vote
1 answer

Count $(a,b)$ pairs such that $a^b\equiv 2 \pmod{p}$

I am working on a problem that requires to count the number of pairs $(a,b)$ such that $$a^b\equiv 2 \pmod{p}$$ Conditions being : $0
1
vote
2 answers

How to justify that the sequence $n^n\bmod 5$ is periodic?

I'm asked in an exercise to give the possible reminders of $n^{n} \bmod 5$ in a congruency that is a good fit for n. After doing so calculations I note that there seems to be a cycle of reminders each $20$ numbers. This is also supported by the…
hhaamm
  • 187
1
vote
2 answers

Find the remainder of $S = \sum_{i=0}^{99} (n+i)^6 + 2^{2^{2558}} + 1$ divided by $100$.

If $n$ is a positive integer, find the remainder of the following number divided by $100$: $$S = \sum_{i=0}^{99} (n+i)^6 + 2^{2^{2558}} + 1$$ I've wrote a program using logarithmic exponentiation and big integers to find that $2^{2^{2558}} \equiv 16…
gareth618
  • 793
1
vote
0 answers

Residue division algorithm

What is the current state of the art method for determining, the residue of a large integer $k$ modulo $m$? The only useful idea I can think of, which Ive seen used in base 10, is if $k$ was written in a positional numeral system with base $p$, and…
Ethan Splaver
  • 10,613
1
vote
3 answers

Equalities modulo a product hold modulo a factor

Is it safe to assume that if $a\equiv b \pmod {35 =5\times7}$ then $a\equiv b\pmod 5$ is also true?
1
vote
2 answers

Prove that $b \equiv c \pmod d$ where $d=\gcd(m,n)$

If $a \equiv b \pmod m $ and $ a \equiv c \pmod n$, Prove that $b \equiv c \pmod d$ where $d=\gcd(m,n)$ We have $a-b=km$ where $k$ is an integer And $a-c=ln$ where $l$ is an integer Now $b-c=ln-km$ What I need to do after this
John757
  • 171
1
vote
0 answers

Question on Least Non-Negative Residue

Suppose we wanted to find the least non-negative residue of, say, $15^{81} \ \text{mod $13$}$, as is a problem in Norman Bigg's Discrete Math text. I know how to solve this by brute-force, but I'm trying to focus a bit more on tricks of the trade…
user465188
1
vote
1 answer

modules concerning Fermat's little thoerem

Suppose $2^a \equiv 2^b\pmod{101}$. Is $a \equiv b \pmod {100}$ always true? The first thing that came in my mind was Fermat's Little Theorem. WLOG $a\ge b$. Since $(101,2)=1$, dividing both sides by $2^b$ gives $$2^{a-b}\equiv 1\pmod {101}$$ Also,…
abc...
  • 4,904