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

Quadratic residues and squares of odd numbers

I wish to know if $\equiv 1 \text{ (mod) }8$ is a necessary and sufficient condition for an odd square number? If not, does there exist a necessary and sufficient criterion for a number to be an odd square? For example $ 14144 x^2+3872 x +265 $ has…
Wilbur
  • 61
0
votes
0 answers

Proving that an expression can never be a perfect square

Is it possible to prove or disprove by modular arithmetic that $$f=\frac{(19(8m\pm1)+1)^2+(22(8m\pm1)+1)^2}{9}$$ can never be a perfect square ($m$ is any integer)? More generally, can a condition be derived on some…
RTn
  • 299
0
votes
0 answers

Congruences mod 3

We have the following congruences: $a^2+2dbc \equiv 0 \mod 3$ $b^2+2ac \equiv 0 \mod 3$ $2ab+dc^2 \equiv 0 \mod 3$ where $a,b,c \in \mathbb{Z}$ and $d$ is a square free integer that is not divisible by $3$ and $d \not \equiv \pm 1 \mod 9$. Deduce…
user289143
  • 4,440
0
votes
1 answer

Primitive element of an irreducible polynomial

Let's consider an irriducible polynomial $f(x)$ over $GF(p^{m})$; i've understood that $f(x) \equiv 0 \space (mod \space f(x))$, however why (intuitively) the polynomial $x$ is considered the primive element of the field ? What's special about the…
AleWolf
  • 185
0
votes
2 answers

Order of a polynomial root

I'm reading this pdf about finite fields. In the first page it's said: Let $α$ be a root of $f(x)$. Then $f(x)|x^{n}-1 \Rightarrow ord(a)|n $ However, what is the order of a root in this case ? And what is the meaning of the implication ? I didn't…
AleWolf
  • 185
0
votes
1 answer

Powers when working with primitive polynomials

When we work with polynomials modulo $m(x)$ where m(x) is a primitive polynomial over $GP(p^{m})$, i know that i can take every coefficient of any polynomial and replace it with it's congruent modulo $p$. (i don't know what's the point in doing…
AleWolf
  • 185
0
votes
1 answer

Polynomial rings and congruence classes

Let's consider the polynomial $m(x)$ over a field $\mathbb{Z}_{3}$. We know that $[m(x)]_{m(x)}=m(a)=0$. Now $m(x)=x^{3}+1$; in my lectures slide, it's said at this point that: $m(a)=0$ implies that $a^{3}=2$. What this means ? Moreover, in the…
AleWolf
  • 185
0
votes
1 answer

Negative integers and polynomial congruence classes

Let's take a polynomial $m(x)$ from $\mathbb{Z}_{3}[x]$. Now, $\mathbb{Z}_{3}$ should contains the integers $-1,-2,-3$. However after reading few exercises about this argument i suspect that we can ignore negative values when we work modulo $m(x)$.…
AleWolf
  • 185
0
votes
1 answer

Polynomials with coefficients in a field

Let's consider this theorem: Let $f(x)$, $g(x)$, $p(x)\in F[x]$ with $p(x)\neq 0$. We say $f(x)$ is congruent to $g(x)$ modulo $p(x)$ if $p(x)$ divides $f(x)−g(x)$, and we write $f(x) \equiv g(x) \pmod{p(x)}$ What's the point in assuring that…
AleWolf
  • 185
0
votes
1 answer

Multiplicative order and powers

Let's consider two number $a$ and $b$ such as $gcd(a,b)=1$. Can you explain me intuitively why there exist $n>0$ such as $a^{n} \equiv 1 \space (mod \space b)$ ?
AleWolf
  • 185
0
votes
0 answers

Computing modular inverses $65537^{-1\!}\bmod (10^n\!-1)$ for large $n$

I have the following formula: $$d \cdot 65537 \equiv 1 \pmod{9999...}$$ I have to find $d$, even in case the modulo is 30 digits long. This means I am not supposed to brute force it, but I haven't yet come across to anything that would help me with…
0
votes
1 answer

Modular aritmetic and fields

I'm studying the concept of field applied to modular aritmetic. Is it correct to say that, if the dimension is a prime number $p$ then field properties are satisfied for the integers $\bmod p$ ? And that, if the dimension is a power of a prime…
AleWolf
  • 185
0
votes
0 answers

Solving a system of congruence equations

Let's consider the system: $\alpha x_1+\beta \equiv 0 \space (mod26)$ $\alpha x_2+\beta \equiv 1 \space (mod26)$ I want to find $\alpha$ and $\beta$ given $x_1, \space x_2$. Subtracting the two equations i get: $\alpha (x_2-x_1) \equiv 1 \space…
AleWolf
  • 185
0
votes
0 answers

Finding the modular inverse of $\alpha$ with respect of 26

I want to prove that given a certain $\alpha$, its modular inverse with respect of 26 ranges between [0,25]. Can you give me an hint ?
AleWolf
  • 185
0
votes
3 answers

Proof that $(a\cdot a)\bmod b=\Big((a\bmod b)\cdot(a\bmod b)\Big)\bmod b$

I'm trying to prove this kinda of trivial modular attribute, but keep failing. $$(a\cdot a)\bmod b=\Big((a\bmod b)\cdot(a\bmod b)\Big)\bmod b$$ Any ideas?
oopsi
  • 165
  • 4