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

Modular multiplicative inverse problem.

I am trying to calculate the multiplicative inverse of big integers of 256 bits and I am not able to find a good calculator to resolve it. I have found some online calculators but the result is not correct. Can someone please help? thanks.
niko
  • 11
1
vote
2 answers

Proof using Fermat's Little Theorem

Use Fermat's Little Theorem to prove that $11|(9n^{23}-5n^{13}+7n^3)$
DewinDell
  • 650
1
vote
3 answers

Question on modular arithmetic

How does one calculate $3^{(29^{10001})} \mod 35$? I'm just not seeing how to start on it, unless someone could give me a hint? Thanks!
simp
  • 883
1
vote
2 answers

Kernel of $f: \mathbb{Z} \rightarrow \mathbb{Z}/7\mathbb{Z} \times \mathbb{Z}/18\mathbb{Z}$ where $f(n) = (3n \bmod 7, 3n \bmod 18)$

I want to find the kernel of $f: \mathbb{Z} \rightarrow \mathbb{Z}/7\mathbb{Z} \times \mathbb{Z}/18\mathbb{Z}$ where $f(n) = (3n \bmod 7, 3n \bmod 18)$ However, it seems to me that I will not be able to $1 \bmod 18$ in any way. Is it because the…
1
vote
1 answer

General solution for $x^2 \equiv x \bmod p$

I want to find a general solution for $x^2 \equiv x \bmod p$, where $p$ is a prime. It is easy to see that if $x \equiv 0 \bmod p$ or $x \equiv 1 \bmod p$ , the equation holds. I got these solutions, but I was not able to figure out any other…
1
vote
4 answers

Find the value of : $24^{6^{2015}} \mod 35$

I want to calculate $24^{6^{2015}}$ mod 35. I found its answer and its correct, but I am not sure if I found it right. It equals 1 mod 35. Here is my calculation: It follows from Euler theorem: $24^{\phi(35)}$ = 1 mod 35. $$ \phi(35) =…
1
vote
2 answers

Why is (-3/77) mod 65 equal to 16?

Getting an X for Chinese Remainder Theorem (CRT) In the "Easy CRT" part of the answer to this problem, the author demonstrates that (-3/77) mod 65 is equal to 16. I don't understand - how is this accurate? I sort of understand the steps, but…
1
vote
0 answers

Divisibility of a number

Find the sum of all four digit natural numbers of the form $4AB8$ which are divisible by $2,3,4,6,8$ and $9$ I know that I can ignore the conditions of 2,3,4 and 6 because checking for divisibility by 8 and 9 would be sufficient to satisfy all…
1
vote
2 answers

Remainder for negative division

How do you calculate the remainder for a division like: $$ (-a) \mod b,\; \mbox{ where } a
k1gabi
  • 13
1
vote
1 answer

Find $n$ in $ \mathbb{N}$ such that : $a^n \equiv 1\pmod {11}$ , such as $ a \in \mathbb{Z}$

$a \in \mathbb{Z}$ , $a$ and 11 are coprime numbers. So due to $Fermat$'s Theorem $a^{10} \equiv 1 \pmod {11} $. So I argued with my math teacher about the solutions of $a^n \equiv 1\pmod {11}$. He said and insisted that the solutions are…
Put Me
  • 393
1
vote
4 answers

How do I find a value for $ 2^{156221} - 1\pmod 9$?

Again the problem is: Calculate the value of: $$\left(2^{156221} - 1\right) \bmod 9$$ I have no idea how to find a solution to this and need help urgently!! Thank you in advance.
Anthony
  • 177
1
vote
2 answers

Problem with a notation in modular arithmetic

I'm reading Grosswald paper and came across something like this: and I don't know what exactly does $(-1/p)=+1$ mean, I'm not much into the subject, and I'm not sure whether it's English notation or just something I don't know. What does this…
Satsuki
  • 51
1
vote
1 answer

How to solve this modular equation that has same varible for mod and inside?

For $m>1$ $$ (m-2)^3\cdot(m+2)^4\equiv 4 \mod m $$ How many possible integers $m$ can be? My modular arithmetic intuition is a bit scarce, so hints and explanations are more appreciated.
user373239
1
vote
4 answers

Show that for every integer $n$, $n^3 - n$ is divisible by 3 using modular arithmetic

Problem: Show that for every integer $n$, $n^3 - n$ is divisible by 3 using modular arithmetic I was also given a hint: $$n \equiv 0 \pmod3\\n \equiv 1 \pmod3\\n \equiv 2 \pmod3$$ But I'm still not sure how that relates to the question.
Jdinh98
  • 33
1
vote
1 answer

$29^{419} \mod 23$ worked example

I just want some confirmation on my method: $$29^{419} \equiv 29^{22*19+1}$$ $$29^{22*19+1} \mod 23$$ Using Euler's theorem, $$\equiv 1^{19} * 29 \mod 23$$ $$\equiv{29} \mod 23$$ $$\equiv 6 \mod 23$$ I am mostly just unfamiliar with powers in…
Inazuma
  • 1,103