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

Group homomorphism preserves identity in modular arithmetic?

Suppose the set of residues $A=\{\bar 1, \bar 3, \bar 4, \bar 5, \bar 9\}$, $f(x,y)=x*y$, $\mathbb Z_{11}$ so the group is $G=\{A, f\}$ in $\mathbb Z_{11}$. The identity is $\bar 1$ as demonstrated by $\bar 3 *\bar 4=\bar{12} =\bar 1$. Suppose…
hhh
  • 5,469
1
vote
1 answer

Modulus Operation on powers of a number by hand

It is fairly straightforward to perform a modulus operation on small numbers by hand, but is there an easy way to find the modulus of larger numbers based on the smaller roots? For example: 180 mod 13 is 11. Is there an easy way to find, by hand,…
cowdrool
  • 147
1
vote
0 answers

Modulus of large numbers

I am learning for an exam and want to understand this: Calculate $3^{142} \mod 50$. Solution: $\operatorname{HCF}(3, 50) = 1$ $\varphi(50) = \varphi(5 \cdot 5 \cdot 2) = \varphi(5^2 \cdot 2) = \varphi(5^2) \cdot \varphi(2) = 20…
1
vote
3 answers

Modular arithmetic problem (mod $13$)

$$\large2017^{(2020^{2015})} \pmod{13}$$ I am practicing for my exam and I can solve almost all problem, but this type of problem is very hard to me. In this case, I have to compute this by modulo $13$.
josf
  • 1,317
1
vote
0 answers

How to find $y$ given $y^a \equiv b \ mod \ p$ and $a,b,p$?

As I understand it the discrete logarithm problem is about identifying $x$ given $a^x \equiv b \ mod \ p$ and $a,b,p$. While researching this I have become interested in the inverted problem, i.e. identifying $y$ given $y^a \equiv b \ mod \ p$ and…
gautam
  • 183
1
vote
2 answers

Compute $(235432_7 \cdot 2551_7) \pmod{311_7} = N_7 = ?$

This is for my assembly language class. I am finding different answers. My answer was $15_7$. But a friend got 2824. Can someone please explain the correct way to do it if $15_7$ is wrong? $$(235432_7 \cdot 2551_7) \pmod{311_7} = N_7 = ?$$
groot
  • 109
1
vote
4 answers

If $a ≡ b \pmod 7$, is $a^2 \equiv b^2 (\bmod 7)$?

Let $a$ and $b$ be integers with $a ≡ b \pmod 7$. Is $a^2 ≡ b^2 \pmod 7$? Justify by giving a proof or a counterexample. I actually have no clue how to even begin tackling this question. How would I go about it?
1
vote
0 answers

Subtracting a finite ring

For the finite ring $R_2 = \{00000000,00000001..,11111111\}$ find: $ 11010111 - 10101010 = N_2 =$___________ I am trying to answer this question. I cannot subtract normally in assembly so, using the formula, i get: (11010111 + ~10101010) mod…
groot
  • 109
1
vote
0 answers

Need help understanding the solution of: Show that there is no perfect square whose last three digits are 341.

Show that there is no perfect square whose last three digits are 341. Solution: Let x be any integer. Note that if $x^2$ ended with the digits 341, then we would have $$x^2 = 1000k+341$$ for some integer k, so $$x^2 = 1000k + 341 = 341 = 5 (mod…
booya
  • 117
  • 8
1
vote
0 answers

Equivalence Clasess modulo n to and exponential

I know that for an equivalence class $$[a]^{[b]_{\phi(m)}}$$ to be well defined, be must be an equivalence class of $\phi(m)$. However, can we always assume that $$[a]^{[b+c]}= [a]^{[b]_{\phi(m)}}[a]^{[c]_{\phi(m)}}$$ And why is that?
1
vote
1 answer

simple RSA decypher

I think my confusion here is just which how the question was given to me. I am having trouble decrypting this simple RSA message. Message: $0882~ 1090~ 1471~ 1899~ 2753~ 0309$ $p = 43 ; q = 71; e = 19$. Someone please check my work that I have so…
Watson
  • 11
1
vote
1 answer

Prove that $3x^3- 7y^3+21 z^3=2$ has no integer solutions.

I have this math problem I'm kind of stuck on. Prove that $3x^3- 7y^3+21 z^3=2$ has no integer solutions. The reason I am stuck on this problem is because I am supposed to be using modular arithmetic to prove it. I'm not really sure where to…
KFC
  • 1,185
  • 6
  • 21
1
vote
3 answers

What is the strategy to finding $\sum_{k=2}^{300} k^k \pmod 7$?

I am stuck on this modular arithmetic problem for homework practice: $$\sum_{k=1}^{300} k^k \pmod 7$$ I am not quite sure how to approach this problem. I've tried finding a pattern between the sums but i do not think there is one. I know how to…
booya
  • 117
  • 8
1
vote
1 answer

congruence with exponential, $ 8^{2012} + 2012^8 $

I have an assignment where the following statement is: Determine the lowest positive integer that is congruent with the statement mod 12: $$ 8^{2012} + 2012^8 $$ How can I solve this? I have totally forgotten...
1
vote
1 answer

Linear Congruences

I understand how to solve an equation like: $$17x \equiv 3 \pmod 5$$ But is there a known method for solving a congruence of the form: $$17 \equiv 3\frac{\sqrt{x}}{2} \pmod 5\quad ?$$ Is it as simple as moving the $x$ through operations and applying…
Char
  • 95