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

modular arithmetic problem (when solving elliptic curves)

Given E: (elliptical curve) $y^2 = x_3+2x+2 \bmod 17$ Recall: $y^2 = x^3+ax+b$ point $P=(5,1)$ Compute: $2P = P+P = (5,1)+(5,1)= (x_3,y_3)$ Now the formula used here is slope $m = \dfrac{3x_1^2 +a}{2y_1}$ and what they got is $s = (2 · 1)^{−1} (3…
1
vote
2 answers

Multiplication of residue classes modulo n

If $\bar{a}$ and $\bar{b}$ are residue classes modulo $n$, it is straightforward to see that $\bar{a} \bar{b} = \overline{ab}$. But given that those classes are sets, does the $=$ mean set equality? To give a concrete example, let $n=7$. Then…
wmnorth
  • 597
1
vote
1 answer

Modular Arithmetic - Changing a Congruence Modulo Relation

Here the solution for $27^{17} \pmod{15}$ is shown. Why is $27 \equiv 12 \pmod{15}$ rewritten as $27 \equiv -3 \pmod{15}$? What is the logic/proof?
1
vote
1 answer

Finding solutions belonging to given field

So I am preparing for a weekly test at my uni and I have a problem like this: Find the solutions of the equations in fields $Z_7, Z_{11}, Z_{13}$. And I'm thinking about the approach for solving such things. Never did that before and what I'd like…
Straightfw
  • 1,558
1
vote
0 answers

If $x=1\mod3$ and $x=0\mod2$, what is it $\mod6$?

If you know what a number mod two different primes is (3 and 2) in this case, how can you tell what the mod is of the two products?
1
vote
1 answer

cost and price profitability analysis

I have been struggling with this question for a long time, Is there somebody kind enough to help? If I received 1 free unit for 3 units purchased, how many units should I sell to issue 1 free unit? The purchase price and the selling price are the…
1
vote
2 answers

Solving a modular equations system

I'm trying to solve the following eqution: $ \left\{ \begin{array}{l l} 5x (mod \space m) = 7\\ 7x (mod \space m) = 5 \end{array} \right. $ for $x$ and $m$. (this is a part from a problem someone gave me to solve: to write a mathematic…
or523
  • 279
  • 2
  • 11
1
vote
1 answer

Modular arithmetics for two equatons

I know the values of $x_1, x_2, y_1, y_2$ and I would like to calculate $a$ and $b$ How do I do it because I have to program the method. $$\begin{align*}x_1\cdot a + b = y_1 \mod 26\\ x_2\cdot a + b = y_2 \mod 26\end{align*}$$
1
vote
0 answers

Solving $a = b^x \mod c$ where $a$, $b$, and $c$ are large integers

I am trying to solve this problem : Given $a$, $b$, $c$ integers (that could be very large), find $x$ integer such as : $a=b^x \mod c$ I tried by coding in C a loop checking the equality and incrementing x, but I assume they are faster ways to…
oursay
  • 11
1
vote
3 answers

Prove that, given integers a, b, and c such that a mod 6 = 3, b mod 8 = 3, and c mod 10 = 3, (a + b + c) mod 6 is odd.

I need to prove that, given integers $a$, $b$, and $c$ such that $a\mod6=3$, $b\mod8=3$, and $c\mod10=3$ then, $(a + b + c) \mod6$ is odd. Here's what I have tried. By using the definition of mod and quotient remainder theorem, I get $a = 6x +…
1
vote
1 answer

Solving $x^5 \equiv 7 \mod 13$

I was taking a look at previous exam papers for my course, and found this question: solve $x^5 \equiv 7 \mod 13$ The solution goes as follows, suppose $\overline{x}^5 = \overline{7}$, then for any m $\overline{x}^{5m} = \overline{7}^m$ from a…
Warz
  • 1,129
1
vote
3 answers

Invertible or zero divisor in $\mathbb Z_n$

Is it true (for $n \le 10$) that every nonzero element in $\mathbb Z_n$ is either invertible or a zero divisor? Can anyone please help me. Thank you
Nayeli
  • 11
  • 1
1
vote
1 answer

Solving the equation $10x = 1 \bmod{9}$

If I have the equation $$10x = 1 \bmod{9},$$ and I'm solving for $x$. I was told the answer is $1$. I don't understand why that is correct. I would solve it like this: Step (1.) $1 \bmod{9} = 1$. Step (2.) $x = 1/10$. How are you supposed…
rubixibuc
  • 125
1
vote
1 answer

Modular exponentiation with Straightforward method

I would like to understand who it works the modulo with Straightforward method. For example I try to test this: 290 mod 1009 = 257^x mod 1009. Which is the "x"? 1 attempt --> 1*257 mod 1009 = 257 2 attempt --> 257*257 mod 1009 = 464 3 attempt -->…
bob
  • 11
1
vote
4 answers

Opposite of mod in a equation

I am trying to solve this module equation (due to a cryptography program that I am coding) but cannot figure it out how: X + 7 % 10 = 6 How Do i solve this? Thanks in advance.
user121590