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

Need Help with Modulus Algebra

Non-mathematician here. I need help solving a formula with a modulus term. First some background: I am trying to calculate the hole positions for a dividing head plate, which is a tool used in the field of machining when cutting gears. The idea…
kdtop
  • 191
1
vote
3 answers

Prove $9^n \equiv 9 \pmod{24}\quad \forall n \in \Bbb N^*$

I accidentally found that $9^n\equiv 9\pmod{24} \quad \forall n \in \Bbb N^*$ But don't know how to prove it in an exact way. Please help
Solitarie
  • 531
1
vote
1 answer

Why is $(k L - y) \mod L = L - y \mod L$?

Why is $(k L - y) \mod L = (L - y) \mod L$? What's the rule that allows the constant $k$ to be ignored?
Paul
  • 113
1
vote
2 answers

Discrete Mathematics - Modular arithmethics

I've been trying to solve a task for some while now but I'm currently very stuck. For the integers $a$ and $b$ it applies that $b \equiv a \pmod{91}$ and $\gcd (a, 91) = 1$. Determine a positive number $k> 1$ such that $b^k \equiv a \pmod{91}.$ I…
1
vote
1 answer

Modulo calculation with inverse and larger divisor

I have this equation $x \equiv (2003^{-1}) \mod 1511$ and am confused with how to try solving it. Since $2003^{-1} < 1511$, you can't use the extended Euclidean algorithm with regards to the inverse. So I'm looking for some tips on where to start…
1
vote
1 answer

Computing $a^r \bmod n$ for a real number $r < 1$

I would like to calculate $d^{1/x} \bmod n$ where $d$ and $x$ belong to $\Bbb Z_n$. Here $x$ is greater than one, thus $1/x$ is less than one. How can I do a computation like that? For example what is the result of $$5^{0,23} \bmod 4?$$ (In fact I…
user58939
1
vote
1 answer

Solution to congruence

I am studying abstract mathematics and I came across this in my textbook. Example: Find a solution to the congruence $$5x\equiv11\pmod{19}$$ It starts off the solution with: If there is a solution, then, by Theorem 3.1.4, there is a solution within…
1
vote
4 answers

$[4]_{17}[x]_{17} = [2]_{17}$: How to optimally solve this equality.

This notation is found in Concrete Introduction to Higher Algebra. Here is my method: For something like $[3]_{11}[x]_{11}^2=[4]_{11}$ I've just been using C++ code like this: #include using namespace std; int main() { for(int j = 1 ;…
1
vote
1 answer

Prove that for any two numbers $0 \leq a < b \leq m - 1$ it is not possible that $m|b - a$

As the title suggest im having difficulty approaching how or where to start proving this. Only thing i can derive from the given is that $m|b - a$ is equivalent to $b - a = mk$ for some k
UnKnoWnZ
  • 167
1
vote
5 answers

Why is -8 $\equiv$ 6 mod 7?

I read in a book that $-8 \equiv 6 \bmod 7$ which means that $-8$ and $6$ leave the same remainder when divided by $7.$ The remainder when $-8$ is divided by $7$ is $-1.$ But when $6$ is divided by $7,$ isn't the remainder $6$? I recognise that we…
PGupta
  • 609
1
vote
1 answer

Solving Quadratic, Cubic and Higher Degree Congruence Equations

I have a question about solving polynomial equations modulo some number. Say we were to solve the following quadratic congruence equation: $$x^2+x + 2 = 0 \quad mod \quad 4$$ We could of course just try the values $0, 1, 2, 3$ and check wheater or…
1
vote
0 answers

Solving an or (linear) congruence system

Usually, when we solve a congruence system, we try to find the general solution that fits the first equation and the second equation and the third, and so on. How should we solve a congruence system such that we find the general solution that fits…
Aladin
  • 702
1
vote
2 answers

What does "Solve $ax \equiv b \pmod{337}$ for $x$" mean?

I have a general question about modular equations: Let's say I have this simple equation: $$ax\equiv b \pmod{337}$$ I need to solve the equation. What does "solve the equation" mean? There are an infinite number of $x$'s that will be correct. Does…
user76508
  • 746
1
vote
1 answer

Modulo expansion with divisor multiples

Is there any general expansion for 'a mod mn' ? mod is modulo operation: http://en.wikipedia.org/wiki/Modulo_operation Eg: we have (a + b ) mod n = ((a mod n) + (b mod n)) mod n (a x b ) mod n = ((a mod n) x (b mod n)) mod n Similarly, Is there any…
1
vote
2 answers

Better way to prove $4^{351012345} \equiv 5^{543213510}$ mod $231$ is true?

The question is to judge whether $4^{351012345} \equiv 5^{543213510}$ mod $231$ is true. I'm thinking of just directly calculating the exact modulus of both numbers using modular exponentiation but is there a better way to prove the equivalence…