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

Does a mod p mod q = a mod q mod p?

How to prove/disprove that (a mod p) mod q = (a mod q)mod p ? Supposing $p < q$, we have 3 situations: $a{\space}{\epsilon}{\space}[0, p)$, obviously the statement is true for this case $a{\space}{\epsilon}{\space}[p,…
1
vote
1 answer

Divisbility and Sum of Nth Powers

Let $S = 1^N + 2^N + \dots + N^N$. Show that $S \ \text{mod} \ N = 0$ for any odd $N$. What would be a good way to start this problem?
1
vote
1 answer

proving: ∀, ∈ ℤ, $2( + )^8 ≡_4 2(^8 + ^8)$

For this question, my way of proving it is: write: $4|(2(\binom80a^8 + \binom81a^7b + \binom82a^6b^2... \binom88b^8) - (2a^8 +2b^8)$ since $2a^8 \ and\ \ 2b^8$ are eliminated, I just need to write $4|(\binom81a^7b + \binom82a^6b^2...\binom87ab^7)$…
1
vote
1 answer

Intuition why $(ab \mod m) = (a\mod m )\times( b\mod m) $

I've had quite easy time imagining why addition would be 'persistent'$\mod m$ but with multiplication it's not that obvious. I've seen proofs of it, but none have helped me internalise it. Any tips on how to think about it? Thanks.
nek28
  • 153
1
vote
2 answers

How to solve such congruences?

Possible Duplicate: HCF/LCM problem Given some positive integers $a_i, a_{i+1},\dots,a_n$ we need to find as large as possible number $X$ such that $a_i \pmod x = a_{i+1} \pmod x = \dots = a_n \pmod x$ I figured out that $X$ will not be greater…
1
vote
3 answers

Prove x is not congruent

If $\,x \not\equiv15\pmod{17},\text{ then }x^5 \not\equiv2\pmod{17}.$ I tried to take the contrapositive: If $\,x^5 \equiv2\pmod{17},\text{ then }x \equiv15\pmod{17}$ and then I assume that $x^5=17y+2$ for some integer $y$ But I am not what to do…
Bryan
  • 725
1
vote
2 answers

2^363 (modulus 7)

Question If today is Wednesday, what day of week will it be in 2^363 days? Okay so I need some way to easily calculate 2^363 (modulus 7). I know that this can be done without the calculator. There are probably some super easy way to solve this,…
1
vote
4 answers

Prove that for positive integer $ n$ we have $169| 3^{3n+3}-26n-27$.

Prove that for positive integer $n$ we have $169| 3^{3n+3}-26n-27$. It is easy to show that if we take the expression modulo $13$ we have $3^{n+3}-26n-27 \equiv 1^{n+1}-1 \equiv 1-1 \mod 13 = 0 \mod 13$. How do I prove it is divisible by $13^2$?
user19405892
  • 15,592
1
vote
5 answers

By what rule or property this expression is equal to six?

$$2^{-1} \equiv 6\mod{11}$$ Sorry for very strange question. I want to understand on which algorithm there is a computation of this expression. Similarly interested in why this expression is equal to two? $$6^{-1} \equiv 2\mod11$$
1
vote
4 answers

Show that $\frac{n(n+1)}{2} ≡ 0\mod n$ for $n$ an odd prime number.

I need help to prove the following question. Show that $\frac{n(n+1)}{2} ≡ 0\mod n$ for $n$ an odd prime number. I have thought about it, since $n$ is odd I can express it as $2k+1$. I can also express $\frac{n(n+1)}{2} ≡ 0\mod n$ as…
1
vote
1 answer

Show that that $x^{\varphi(pq)/\gcd(p-1,q-1)}\equiv 1\mod pq$ for all $x\in (\mathbb Z/pq\mathbb Z)^\times$

If $p$ and $q$ are distinct odd primes, how could I approach showing that $x^{\varphi(pq)/\gcd(p-1,q-1)}\equiv 1\pmod {pq}$ for all $x\in (\mathbb Z/pq\mathbb Z)^\times$? I understand that $\varphi(pq)=(p-1)(q-1)$. I've shown separately that…
GPhys
  • 1,539
1
vote
3 answers

Solve $22t \equiv 9 \pmod{7}$

I am trying to solve a modular arithmetic system and I got to the point where I have to solve $22t \equiv 9 \pmod{7}$ for $t$. I researched on the internet and found that there are many ways to solve this, such as using linear diophantine equations,…
Amous
  • 235
1
vote
1 answer

Given k % y, how can I adjust the dividend (k) to preserve the modulo when the divisor (y) is incremented by one?

In a programming algorithm, I'm using the result of k % y. I need to understand how to adjust k when the value of y is incremented by one to preserve the same modulo result. In other words, solve for x: (k + x) % (y + 1) = k % y Empirically, I see…
MikeBRM
  • 13
1
vote
1 answer

Find last two digits using modular arithmetic

Find the last two digits of $7^{7^{7^{10217}}}$. We need to find $7^{7^{7^{10217}}}$ (mod $100$) and $\phi(100) = 40$ So $7^{40} \equiv 1$(mod$100$) I don't know how to proceed after this
Gauri Sharma
  • 816
  • 5
  • 17
1
vote
1 answer

Is there a theorem based on substitution to convert a congruency to an equality?

I am working on my own version of a proof of RSA and have come do a conclusion based on these simplified statements. Given: N = pq X ≡ 1 (mod p) X ≡ 1 (mod q) X ≡ 1 (mod N) by chinese remainder theorem I have the original expression: MX ≡ M' (mod…
dhatch387
  • 155