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

Powers of elements congruent to primes.

Given: $p$ is a prime number. $r > 1$ is an integer. $m$ is an integer such that $p \nmid m$ (i.e., $p$ does not divide $m$). $x^m \equiv 1 \mod p^r$ and $x \equiv 1 \mod p$. Goal: Prove that $x \equiv 1 \mod p^r$. So far I am considering the…
0
votes
0 answers

Formalize a statement about the amount of residue classes

I have a set of residueclasses mod $m$, e.g. with $m=11$ one could have the set $M=\left\{[2]_{11}, [5]_{11}, [6]_{11}, [10]_{11}\right\}$. Now I define a ratio $\operatorname{d} :=\frac{\#M}{m} = \frac{4}{11}$. So in this set I find all the number…
Lereu
  • 424
0
votes
1 answer

Suppose that a and b are integers, a $\equiv$ 11 (mod 19) and b $\equiv$ 3 (mod 19). Find the integer c such that c $\equiv$ a - b (mod 19).

With $0 \le c \le 18$. I can recall the basic modulo arithmetic properties, but I can't see how to apply them. Any help would be appreciated.
xvymnp
  • 33
0
votes
1 answer

How to find the inverse element to a number in the residue ring modulo

I don't understand how to find the inverse element to $7$ in the residue ring modulo $449$. According to Euclid's algorithm, I get $-64$, although the answer should be the number $385$. But at the same time $-64 + 449 = 385$. But how do I get $385$…
0
votes
1 answer

Find the remainder when $2^{2^{24}}$ is divided by 9

Find the remainder when $2^{2^{24}}$ is divided by 9 My approach is as follow $2^{2^{24}}=4^{12}$ Hence we can write is as $2^{2^{24}}=2^{4^{12}}=16^{12}$ $16^{12}=(9+7)^{12}$ We get remainder as $7^{12}$ Now $7^{12}=(9-2)^{12}$ We get remainder as…
0
votes
0 answers

How to prove that $2^{x+2} | 3^{2^x} - 1$ is true for all natural x greater than zero

Actually, I don't know it's true or not. I just make observation and write simple python script that checked this for x belongs to [1, 50] and it's alright. Can somebody tell it is true or not and if it is true, how I can prove this?
0
votes
0 answers

Quadratic congruence equation: must I use trial & error?

So I'm studying number theory, and my book said that $$ x^2 + 5x + 7 \equiv 0 \pmod n $$ had at least four solutions for 1
Daniel
  • 273
  • 1
  • 9
0
votes
1 answer

Generalization of same numbers in modulo?

Is there a way to predict the same occurring numbers between two modulo sequence ? Let me take an example Here are the first 21 numbers of the sequence A with modulo 7: 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 …
LeXav
  • 3
0
votes
1 answer

Simple Proof as part of Merkle-Hellman

I'm implementing a Merkle-Hellman cryptosystem and I have a question about a small detail. In order for it to work, all potential subsets of the super-increasing sequence must have distinct sums. That is very easy to prove because the set is…
Patrick
  • 3
  • 1
0
votes
0 answers

How do I prove that the square of a non-multiple of 3 is always 1 mod 3?

So I have this very simple modular arithmetic question: How do I prove that squares of a non multiple of 3 is always congruent to 1 mod 3? In math terms, how do I prove for $n \not\equiv 0 \pmod{3}$, $n^2 \equiv 1 \pmod{3}$ Might seem a little…
0
votes
0 answers

simplyfing modular equations

Are there other ways of symplifing equations? $\qquad$ Finding the inverse: $ 42 y\equiv1 \bmod 5 \qquad 42 =5(8)+2 \qquad 5 = 2(2) +1 \qquad 2=1(2) \implies 1 = (17)5+42(-2) \implies x \equiv -2 \bmod 5 $ This method works because of Bezout’s…
0
votes
0 answers

Solving modular equation with multiplication

Let's imagine I have the following equation: (x * b) % m == a I know a, b and m and want to solve for x. I know that if I could find the modular inverse of b (mod m), it's trivially solvable. In some cases however, modular inverse is not defined,…
unbeli
  • 109
0
votes
0 answers

How to factorize values that include modular arithmetic?

I have an equation: $b*(x*rinv*s*b\mod n) - (x*b)$ In which i need to isolate x but when i do: $ x*(rinv*s*b \mod n) - b)$ The results are different, Why? Here are the values: x =…
0
votes
0 answers

Proving that simple polynomials with an integer solution can always be solved with modular arithmetic.

Using this equation as an example $$5 x^2 + 7 x - 66 = 0$$ It has x=3 as a solution (also -4.4 but we'll ignore that). Apparently we can solve this using modular arithmetic for any modulus. E.g. for modulus=4 we have $$1 \cdot x^2 + 3 x - 2 \equiv…
Daniel
  • 273
  • 1
  • 9
0
votes
0 answers

Solving congruence how to ensure that I always have the base answer

I am practising solving congruence and have found that my method doesn't always give me the lowest possible answer. I assume the process below would find the lowest possible answer, but I checked and 2 is the lowest. What step am I missing in this…