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

How to normalize numbers, so that they range from 0 to 23?

I am trying to normalize the day time of Minecraft. There are 24000 ticks per in game day, so I can chop of the trailing zeros. But the issue is, that 18000 is midnight, which doesn't make sense. So I want to have midnight as…
Apollo
  • 121
2
votes
1 answer

how to solve $ax+by=c \mod p$?

Given $a$, $b$, $c$ (integers), and $p$ (prime), Is there any general solution for $ax+by=c \mod p$? I found that it has similar form to solving $ax=c \mod p$, but cannot find the connection between these two.
user4478
  • 329
2
votes
1 answer

Solving $x^2 \equiv 106234249 \bmod{12^2}$

I have the following congruence: $$x^2 \equiv 106234249 \bmod{12^2}$$ When I tried to solve it, the equation becames in 2 equations: $x^2 \equiv 4 \bmod{9}$ $x^2 \equiv 9 \bmod{16}$ Because $12^2 = 9 \times 16$ and, 9 and 16 are coprimes. Then I…
2
votes
2 answers

Math Parlor Trick

A magician asks a person in the audience to think of a number $\overline {abc}$. He then asks them to sum up $\overline{acb}, \overline{bac}, \overline{bca}, \overline{cab}, \overline{cba}$ and reveal the result. Suppose it is $3194$. What was the…
Gerard
  • 4,264
2
votes
1 answer

Concerning some properties of Modular Arithmetic.

Recently I came across a Wikipedia page concerning Modular Arithmetic. Some properties were stated there, but without any proof. I tried solving them. Most were solved but I got stuck up in two of them. They are:- 1.If a ≡ b (mod n), then p(a) ≡…
2
votes
0 answers

How do you address cases in modular arithmetic where the input is greater than the modulus?

I'm not sure how well I'm wording this, but I was wondering how you address cases in modular arithmetic when you plug in a number greater than the modulus, e g. $\sqrt{8} \pmod{5}$. If you leave $8$ as it is, and square root it, you get…
e4494s
  • 475
  • 2
  • 5
2
votes
2 answers

How to prove that $x + y \equiv 4\pmod 6 $

Prove that if x and y are integers such that $x \equiv 3 \pmod{12}$ and $y \equiv 7\pmod{18}$, then $x + y \equiv 4\pmod6$ I tried making the equations into algebraic equations. So, $x\equiv3\pmod{12}$ becomes $x=3+12p$ for $p\in…
Bryan Hii
  • 325
2
votes
3 answers

How to solve modulo equations

I was hoping someone would help me on how to solve the following modulo equations (they are from an exercise book in my course which unfortunately is without conclusion): (1) $x^{2018}=1 \pmod {21}$ (2) $5x^{2107}=75 \pmod {205}$ For (1) I have…
kabin
  • 391
  • 1
  • 6
2
votes
4 answers

Congruence relation possible typo?

Is the following a typo? If $a \equiv b \pmod{m}$, then for some scalar $c>0$, $ac \equiv bc \pmod{mc}$ Or should it be $\pmod{m}$?
2
votes
1 answer

How to compute the remainder of a division $a/b$ to a modulus $M$, i.e. $a/b \pmod M$

I am learning the usage of mod in programming to overcome the overflows. I was able to deduce the following relation ships: for example if I want to perform addition between $a$ and $b$ and the result must be modulo to M then i can perform the above…
2
votes
1 answer

Rounding a number up to the nearest multiple of an integer

Suppose I have a number $x$, and I want to round $x$ up to the next multiple of $y$ if $x$ isn't already divisible by $y$. I tried $x + y - (x \mod y)$, but this fails when $x$ is already divisible by $y$. e.g., if $x = 6$ and $y = 3$, then $x + y -…
24n8
  • 1,455
2
votes
1 answer

Can you move a clock's hand by a constant, such that the hand hits all angles

My younger brother asked me if rotating a clock's hand by $\pi$ degrees (or any irrational number) would mean that the clock's hand would eventually point at all angles. Initially I though that could be correct. After all, $\pi \cdot n$ is…
Alex P.
  • 123
2
votes
1 answer

Find the residue of the following number

Find the residue : \begin{equation} 1^{965}+2^{965}+...+2018^{965} \equiv x\ (\textrm{mod}\ 2021), x=? \end{equation} My attempt so far: \begin{equation} \varphi(965)=\varphi(5)\varphi(193)=768. \end{equation} But from Euler theorem applied for…
Moscow1
  • 49
2
votes
0 answers

How to operate on Cyclic groups?

Zq* is a cyclic group generated by g order q. In other words, there exists g in Zq* such that Zq* = {1, g, gˆ2, gˆ3, . . . , gˆ(q-2)} mod q = {1,2,3,...,(q-1)} mod q. Such a "g" is called a generator of Z. Example: in Z7* is generated by g=3,…
2
votes
2 answers

Modular Arithmetic Inverse Proof

Let $m, x$ be positive integers such that $\gcd(m, x) = 1$. Then $x$ has a multiplicative inverse modulo $m$, and it is unique (modulo $m$). Proof: Consider the sequence of $m$ numbers $0, x, 2x, \dots, (m−1)x$. We claim that these are all distinct…