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

How to solve modular arithmetics problems, that are not linear?

$2x^{20} + 3x + 4 \equiv 0 $(mod 176) I know the answer is $x = 176k + 20$, $k \in \mathbb{Z}$ , but I don't know, how to solve this problem.
0
votes
1 answer

How to find all integer $x$ such that $x^{2}+5145x+2332\equiv 0\pmod{ 9797}$

How to find all integer $x$ such that $x^{2}+5145x+2332\equiv 0\pmod{ 9797}$. I think $9797$ can factor, then $9797=97\cdot11$. So I can convert to $$x^{2}+5145x+2332\equiv 0\pmod{97}$$ $$x^{2}+5145x+2332\equiv 0\pmod{11}$$ How do to next? Thanks.
Kölle
  • 11
0
votes
0 answers

Custom RNG : Modular Arithmetic Equation

I'm trying to recover the internal state of a custom RNG in order to predict the next state. The formula to compute the next state is as follow : $nextState = (state * A + B) \mod p$ The value of p is the 9th mersenne prime ( $2^{61}-1$ ) A and B…
Babar
  • 1
0
votes
1 answer

Determine necessary and sufficient conditions on $x, N$ so that the following holds: for any $a, b$, if $ax ≡ bx \pmod N$, then $a ≡ b\pmod N$

Been working on it for a couple of hours with no success. My intuition tells me that it has to do something about $\gcd(n,x) = 1$ I have managed to prove that if $\gcd(x,n) = 1$ the claim holds, now I try to prove the other way around. Any hint or a…
alon1230
  • 35
  • 3
0
votes
2 answers

Question about conguence module m: If $n> 0$ and $n$ is not a multiple of $3$, prove that $a = 3^{2n} + 3^n + 1$ is divisible by $13.$

I would like to solve this problem using the idea of congruence module m, but I have no idea how to start. Could someone help me? If $n> 0$ and $n$ is not a multiple of $3$, prove that $a = 3^{2n} + 3^n + 1$ is divisible by $13$.
Thais
  • 65
0
votes
1 answer

Difficulties with Modulus - Chinese Remainder Theorem, GCD and the Extended Euclidean Algorithm

I am finding it quite difficult to deconstruct the steps for seemingly simple questions and decide which mathematical process to use. For example If $x \equiv 2$ (mod $11$) and $ x \equiv 1$ (mod $17$), what is the value of $x$ (mod $187$)? There…
Catwth
  • 9
0
votes
2 answers

Show that $0, 1, 2, 2^2,...,2^9$ form a complete residue system 11 module.

I have question about module congruence Show that $0, 1, 2, 2^2,...,2^9$ form a complete residue system 11 module. I have no idea or where to begin to resolve this question. Can anybody help me? Thanks.
Thais
  • 65
0
votes
0 answers

Identifying a Modular Exponent

Let's say I'm given a number. I am now asked to determine if this number is of the form : $a^{b}$ mod $N$ . Unfortunately the parameters are such that I cannot perform a discrete logarithm in feasible time. $a$ and $N$ are known (and large) natural…
0
votes
0 answers

$ \forall\;n\;<\;3 \;$,$ \exists \;(a;b;c)$ such as $ a^n+b^n=c^n$ and, specifically $4693^{20}+4110^{20}\neq4709^{20}$

I'm working on Fermat property that says that : $\forall \; n\geq3, \; \nexists \;(a;b;c)$ such as $ a^n+b^n=c^n $ I am asked to prove that it is necessary to use congruences greater or equal to 7 in order to prove that…
philok
  • 21
0
votes
1 answer

Homomorphism between $\mathbb{Z}_m$ and $\mathbb{Z}_n$ if $m\mid n$

How can I show $\phi:\mathbb{Z}_m \to \mathbb{Z}_n$ defined by $$ \phi(k) = k\mod{n} $$ satisfies $\phi(k +_m l) = \phi(k)+_n \phi(l)$ when $n\mid m$. I have tried using remainder terms but the solution gets messy as I have mod n's and m's and cant…
math111
  • 326
0
votes
1 answer

Finding the smallest number $a \geq 0$ such that $a \equiv 7^{83} \bmod 11$.

Find the smallest number $a \geq 0$ such that $a \equiv 7^{83} \bmod 11$. I know that I am supposed to come to the conclusion $a = 2$, but I don't understand how I reach this conclusion using Fermat's or Euler's theorem. I have the order $83$ to…
Mampenda
  • 409
0
votes
2 answers

For $x^2 + x + 1 \equiv 0 \pmod 5$, either find a solution $x \in \mathbb{Z}$ or show that no solution exists.

Find a solution $x \in \mathbb{Z}$ or show that no solution exists. $x^2 + x + 1 \equiv 0 \pmod 5$ So far I have been trying to the Chinese Remainder Theorem to solve this question but I still can't figure out the answer; I'm not sure whether I used…
0
votes
2 answers

How can I prove they are congruent?

if $m$ is an integer and $\gcd(m,3)=1$,prove that $m^7\equiv m \pmod {63} $. I try using Fermat's Little Theorem,but it doesn't work. Please help me.
CHI NEW
  • 63
0
votes
3 answers

$437$ divides $16^{99} -1$. Help to finish it.

I am doing an exercise and find a question which I can't answer. The exercise asks to show that $16^{99}\equiv 1 \pmod{437}$. Since $\gcd(16,437)=1$, Euler's theorem says $$ 16^{\varphi (437)}\equiv 1\pmod{437} \Rightarrow $$$$16^{396}\equiv…
Senna
  • 1,233
0
votes
1 answer

Solving congruence problem

Let $p$ be a prime number of the form $4n+1$, and let $n$ be a natural number. Show that congruence $x^2\cong-1 \mod p$ is solvable. I tried solving by simplifying $\cong$ sing i.e. $x^2 + 1 = p.m$ or $x^2 = (4n+1).m -1$. But I can't proceed after…
goku
  • 99