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

Simplifying and solving a complex system of modular arithmetic expressions

I have the following system of 2 equations: $1956483837 = (13179379638883309848L+(c_0+ 3048033998+1)+ 1)\ mod\ (2^{32} )$(1) $2973671708 =(15447106725414132384+3912967674*((d_0+ 3659326121)\& 0xffffffff)+891235890+((((c_0+ 3048033998+ 1)\&…
S. L.
  • 157
1
vote
0 answers

Modular arithmetic help?

I don't even know if this really falls into the category of modular arithmetic, but I wouldn't know what to call it since I don't have a formal math education. Let’s say we know the resulting values of the following equations: $$(x-a)\…
1
vote
1 answer

Is this Modular arithmetic property true?

If $a \equiv b \mod (nm)$, then is it always true that $$a \equiv b \mod n$$ $$a \equiv b \mod m$$ I feel like it's kind of obvious because if $a-b = k_1nm$, then $a-b = k_2n$, ($k_2 = k_1n$) but I can't find any resources on the topic, so maybe I'm…
1
vote
3 answers

Prove that if a ≡ b mod m and c ≡ d mod m, then ac ≡ bd mod m.

Prove that if a ≡ b mod m and c ≡ d mod m, then ac ≡ bd mod m. In previous attempts I have tried to express a as b + mk and c as d + ml and I have also shown that m|a-b and m|c-d but I was unable to reach a complete proof. Just a problem I have…
global05
  • 814
1
vote
1 answer

Primitive Root Modular Arithmetic Question

3)Given a prime $p$ and an integer $a$, we say that $a$ is a $\textit{primitive root} \pmod p$ if the set $\{a,a^2,a^3,\ldots,a^{p-1}\}$ contains exactly one element congruent to each of $1,2,3,\ldots,p-1\pmod p$. For example, $2$ is a primitive…
a23
  • 149
1
vote
0 answers

solving a function where [x mod y represents the remainder after division of x by y]

I would like help solving this practice question. For a function f(x, y) defined below, what is the value of f(775, 527)? Here, x mod y represents the remainder after division of x by y. f(x, y): if y = 0 then return x else return f(y, x mod…
Edison
  • 131
1
vote
1 answer

Looking for a special hash function

I am looking for a special function, which could change itself (for example other constants set) so that part of its output would change in a special way. Let it be such that at the beginning, the function would be just identity x -> x for x in…
snamef
  • 11
1
vote
0 answers

Finding an expression relating two congruence moduli

Suppose I have a positive integer $a$ which can be written as $\equiv n (mod) t$ for some $n$ and $t$. Now if I have another integer $b$ related to $a$ as: $b=\sqrt{(2t+1)a^2+t^2}$, and I can write $b \equiv o (mod) t$; then does there exist a…
RTn
  • 299
1
vote
2 answers

making $p$ the subject in $(3n + p) \bmod4 = 0$, how?

Let n and p be any positive integer, make $p$ the subject of the equation: $(3n + p)\bmod4 = 0$. How is it done? I've worked out that the only values for p are 1, 2, 3 and 0. This formula is for calculating the amount of padding required in a…
meiryo
  • 875
1
vote
2 answers

Are there some known results for solving this kind of modular arithmetic problem?

Preliminaries Consider a number in the form: $$x = a^n b - c,$$ where $a, b, c$ and $n$ are natural numbers. For which $n$ we can say that $x$ is divisible by $d$ with $a$ and $d$ coprime? WLOG, consider the following example with $a=2$, $c=1$…
the_candyman
  • 14,064
  • 4
  • 35
  • 62
1
vote
3 answers

How can I prove that $\left\lceil \frac{4N}{3} \right\rceil \bmod 4 \ne 1$?

Ok this is for Base $64$ padding. The length of Base $64$ representation of a sequence of bytes is represented by $\left\lceil \frac{4N}{3} \right\rceil$ The padding should add $M$ characters such that $$\frac{\left(\left\lceil \frac{4N}{3}…
1
vote
1 answer

Square root congruence equation: solving for the modulus

I'm trying to solve a system of the type $a^2 \mod n \equiv b\\ b^2 \mod n \equiv c\\ c^2 \mod n \equiv d\\ ...$ Where $n = p q$ for some primes $p$ and $q$. I know how to solve these systems when the unknown is $a$, but here the unknown is $n$.…
Sam
  • 13
1
vote
2 answers

How to calculate an editor cursor position?

I'm creating an audio editor and the scroll/cursor position is going wonky at the end. Let me set up the scenario. -I know how many pixels is equivalent to 1 second of audio time. Call it $oneTickWidth$ . -I have a window that the viewer can see at…
1
vote
3 answers

If $\gcd(a,N)=1$, why is it that the base $a$ will produce at least one instance of a power equal to $1\pmod N$?

I'm familiar with Fermat's Little Theorem and Euler's Totient, but I'm wondering whether the fact that the only shared factor of $(a,N)=1$ has something to do with the fact that, given the prior constraints there exists at least one $x$ (with $x$…
JohnGalt
  • 189
1
vote
2 answers

Reducing the mod value itself (modular calculus)

I wrote an algorithm by combining Fermat's Little Theorem and Euler's Method. However, I am experiencing a problem in Euler's method. For instance, If I take $(A, B, M)$ such that $A^B mod(M)$. When the initial values are $(12341, 123141, 12313)$…
seVenVo1d
  • 452