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

Find the smallest natural number $x$ which satisfies both $5x \equiv 4$ mod $13$ and $4x \equiv 5$ mod $17$

Using the multiplicative inverse of 5 (which I used $8$), and multiplying it to $5x \equiv 4$ mod $13$, I get $x \equiv 6$ mod $13$. From that I get $x=13k+6$. Plugging that into $4x \equiv 5$ mod $17$ and simplifying, I got $k\equiv 15$ mod $17$.…
1
vote
2 answers

find remainder using modulo arithmetic

what is the remainder when $55^{142}$ is divided by 143? Initially I wanted to use Fermat's little theorem but 143 is not prime. Euler's theorem does not seem to work here either as $(55,143)\neq 1$ The answer is 55. Any ideas how to proceed?
H.E
  • 2,056
1
vote
0 answers

Modular exponentiation to shuffle list

Can modular exponentiation be used to shuffle a list? I have noticed that modular exponentiation sometimes repeats every number only once, and therefore works like a shuffle mechanism for a list. I do not exactly know within what constraints it does…
1
vote
0 answers

Prove $(p-2)^{(2p-1)^{n}} \equiv (p-1)^{(2p+1)^{n}} -1\pmod{p(p-1)}$

Prove: $(p-2)^{(2p-1)^{n}} \equiv (p-1)^{(2p+1)^{n}} -1($mod $ p(p-1)) $ , where $p$ is a prime number and $n$ is a natural number. This congruence mod operation problem was formulated by Leon Rosenfeld in 1923. Attempt: The only idea I had was…
1
vote
1 answer

Solving modular equations for solutions.

Given $k, p, q$, we need to find the solutions for $x ^{k}\equiv p$ (mod $q)$. How to find the number of solutions for $x$ up to some upper limit of $x$.
1
vote
1 answer

Modulus between different fields

If I have a value: A mod P, where P is a prime number, and A=a*b*c*d.... n elements. Is there a way to transform this product modulo some other number which is co-prime to P. Like A mod M. Or will I have to do all multiplications over again? what if…
Salena
  • 638
1
vote
0 answers

Prove that the rule $f([a]_{mn}) = ([a]_m,[a]_n)$ determines a well-defined function $f : Z/mnZ \to Z/mZ × Z/nZ.$

I think it is well defined because of the fact that it will always produce a unique output. Even if [a]_2 repeats as the first term where mn is even, [a]_n will be unique so the output itself will be unique. Is this thinking correct?
1
vote
0 answers

Smallest number that satisfies set of modulo inequalities (incongruences?)

Suppose I want to find the smallest $x$ that satisfies the following set of equations: $$ \left(x+a_1\right)\mod{d_1} \not\equiv 0 \\ \left(x+a_2\right)\mod{d_2} \not\equiv 0 \\ \left(x+a_3\right)\mod{d_3} \not\equiv 0 \\ \vdots $$ Is there a way to…
janreggie
  • 111
1
vote
0 answers

How should I read the equation $a \equiv b \pmod p$? Is it $a$ or $b$ the remainder?

I'm having quite a bit of confusion over how I should read the congruent sign in a modulus equation. For example, I have seen this example as valid: $$ 81 \equiv 13 \pmod{17} $$ From what I see, it reads to me as "when $81$ is divided by $17$, the…
xenon
  • 3,438
1
vote
1 answer

How many times does clock B show the right time?

There are two analog clocks. Clock A works as normal, but clock B goes backward and seven times as fast. How many times in 24 hours will clock B show the right time (same as A). Meaning how many times do the short hands align? I found similar…
1
vote
0 answers

Quadratic congruence equation of form $aX^{2} + bX \equiv c$(mod m)

So far i only encountered linear congruence equations of the form $aX \equiv b$(mod m) or $aX^{2}+bX+c \equiv 0$(mod m). I can't find any answers on how to proceed with this kind of equation. Any tip or hint would help.
1
vote
1 answer

The largest negative number that fulfills the congruence equation 8x+7≡3 mod 35

So as an exercise I'm trying to figure out which largest negative fulfills 8x+7≡3 (mod 35) I have solved the x, x=17, but honestly I have no idea where to go from here. Maybe 17-35=(-18)? I'd appreciate any pointers and help. Thanks for your time.
Talar
  • 35
  • 5
1
vote
1 answer

How is the following relation involving modulo operation equal?

Why does the following equation hold? $$\frac{2^{lk}-1}{2^l-1}\bmod p=(2^{lk}-1)(2^l-1)^{p-2} \bmod p,$$ where $p=100000007$ That is (in more standard mathematical notation), $$\frac{2^{lk}-1}{2^l-1}\equiv (2^{lk}-1)(2^l-1)^{p-2} \pmod p$$ Does this…
user74207
  • 197
1
vote
0 answers

Use of mod 97 for generating check digits

All International Bank Account Numbers (IBANs) include two check digits that are the result of taking an intermediate value mod 97. Similarly, in France mod 97 is used to generate the National Check Digits for the national account number. 97 is the…
1
vote
1 answer

Arithmetic sequence modulo a prime number

I am not a mathematician or a math student, but an electrical engineer. I have noticed that an arithmetic sequence modulo a prime number p contains every integer between zero and that prime number if the arithmetic sequence has at least p elements…
DavidG25
  • 111