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

Solving equations with mod 1 numbers and multiple variables

I have two numbers (inputs): $ca$ and $cb$ and an expected result (output): $cc$. All of those are $mod 1$ numbers, usually represented as fractions like $\frac ab$ where $a$ and $b$ are integers, e.g. $\frac{5}{32}$. I can add, subtract, and…
user2312896
  • 111
  • 1
1
vote
1 answer

How to solve $x^2+y^2 \equiv 8\pmod 9$?

How to solve $x^2+y^2 \equiv 8 \pmod 9$? I know the Chinese Remainder Theorem, but how do I apply it here?
Rhea
  • 87
1
vote
3 answers

What is the remainder of $2019^{2021}$ divided by 11

With these kinds of problems, I use congruence, and I aim to get the remainder to be -1, which then gets me pretty close to the solution. On this one I'm kinda stuck. Can't get to that -1.
Gruja
  • 107
1
vote
1 answer

Condition on a quadratic equation to be an odd perfect square using modular arithmetic

As a result of the discussion in this question Quadratic residues and squares of odd numbers, @Mark Bennet asked me to open this question. I have a quadratic expression $14144x^2+3872x+265$. How can I prove that this is never a perfect square using…
Wilbur
  • 61
1
vote
3 answers

Modular Arithmetic. Integer Solutions

How can you show that $|a^2 -10b^2|=2$ has no integer solutions for a and b using modular arithmetic? Thank you.
Maths
  • 43
1
vote
0 answers

Question regarding Sum of squares in modular arithmetic

Based on my previous question which turned out to be regarding modular arithmetic, I have another question: I have two functions $$f_1=\sqrt{\left(\frac{19(8m-1)+1}{3}\right)^2+\left(\frac{22(8m-1)+1}{3}\right)^2}$$ and…
RTn
  • 299
1
vote
4 answers

Show that $x^2+1$ is not divisible by 19 using modular arithmetic

I am learning how to use modular arithmetic and am struggling. I approached the problem by letting $x=19k+r$ and then showing we cannot factor out 19 when considering all the remainders. What is a more efficient solution using modular arithmetic?
dragonking
  • 125
  • 4
1
vote
0 answers

Find $x$ satisfying $x^a\ \textrm{mod}\ b \geq c$ where $a$, $b$, and $c$ are known

If $a$, $b$, and $c$ are known, is there an efficient way to find values of $x$ which satisfy $x^a\ \textrm{mod}\ b \geq c$ ?
1
vote
1 answer

Use congruence to show that the output of a natural number function is always divisible by 6

I have been asked to show that for any natural number $n$, $(7n+30)(13n+7)(n+2)$ is divisible by 6. I can show that this function is congruent to $n(n+1)(n+2)$. I noticed that this function is the sequence of tetrahedral numbers multiplied by 6…
1
vote
1 answer

Why $gcd(\alpha,26)\neq 1$ means that $ax\equiv y \pmod{26}$ is not injective?

Let's consider the equivalence: $ax\equiv y \pmod{26}$ If $gcd(\alpha,26)\equiv 1$ I can multiply each member by $a^{-1}$ and i can obtain $x$ in function of $y$. If $gcd(\alpha,26)\neq 1$ i can't find the modular inverse, however what assures us…
AleWolf
  • 185
1
vote
3 answers

A question about modulo with high number

The question I got is $$ 42^{27} \bmod 55 $$ And the answer I got is like this $$ 42(42^{2})^{13} \bmod 55 \\42(1764)^{13} \bmod 55 \\42(4)^{13} \bmod 55 \\42(67108864) \bmod 55 \\42(9) \bmod 55 \\378 \bmod 55 \\ 48 \bmod 55 $$ So on the…
Tevil
  • 45
1
vote
1 answer

Given that $d$ divides $n$, what is $d + \frac{n}{d} \pmod 4$

As the question titles states, how can I efficiently find whether $d + \frac{n}{d} \equiv 0 \pmod 4$, given that $d$ divides $n$? An example would be with $n = 35$ and $d = 5$. $5 + \frac{35}{5} = 5+7 = 12 \equiv 0 \pmod 4$, so it "passes". I tried…
1
vote
1 answer

Division in modular arithmetic when multiplicative inverse does not exist

Lets suppose we have two integers $a$ and $b$ such that $b\mid a$ and an integer $p$ that is not co-prime with $b$. In that case, $b^{-1}$ does not exist in $\mathbb{Z_p}$, but there is an integer number, let's call it $c$, that satisfy the relation…
1
vote
5 answers

$11x + 13 \equiv 4$ (mod 37)

$11x + 13 \equiv 4$ (mod 37) My "solution" to the problem $11x + 13 \equiv 4$ (mod 37) $\rightarrow$ $11x + 13 = 4 + 37y $ $11x - 37y = - 9$ Euclid's algorithm. $37 = 11*3 + 4$ $11 = 4*2 + 3$ $4 = 3*1 + 1 \rightarrow GCD(37,11) = 1$ $3 = 1*3 +…
1
vote
2 answers

Is it true that $a^k\equiv a^\ell \mod n$?

Let $a, b\in\mathbb{Z}$, $n\in\mathbb{N}$, and $k, \ell\in \mathbb{N}$, such that $k\equiv \ell \mod{n}$ and $a\equiv b\mod n$. Is it true that $a^k\equiv a^\ell \mod n$? If so, prove it. If not, find a counterexample. I suppose it's true, but I'm…