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

continuing congruence equation

How do you solve this congruence equation? $$3\equiv -4a\pmod {13}$$ What I did was : Applying symmetry property $$ -4a\equiv 3\pmod {13} $$ Since gcd(13,4) = 1 we multiply both sides by inverse of $4\pmod {13}$…
user566838
0
votes
2 answers

Question about modulus order of operations

I have maybe a simple question but I haven't been able to find an answer through googling. The question is as such: Is $\ a × b^2 \bmod c $ the same as $\ (a \bmod c) × (b^2 \bmod c) $? That's it. That's all I'm confused about. Sorry if it seems…
user565034
0
votes
2 answers

How do I calculate the reminder (mod)

I want to calculate the reminder for high power value using casio (fx-991es) Ex: $$ 87^{17} \ \bmod 77 $$ This method not working because the number is too large Ex: $$ 9/2=4.5= 4-4.5=0.5= 0.5*2=1 $$
Mahmood
  • 19
  • 1
0
votes
2 answers

How to find $x$, knowing $e$, $p$, and $x^e\bmod p$?

How would you find $x$ in a modulo arithmetic expression $x^e \bmod p$ knowing only $e$ and $p$? $e$ is an integer, $0 \leq e \lt p$, that is relatively prime to $p-1$; and $x$ is an integer, $0 \leq x < p$.
user8442
0
votes
2 answers

Why isn't $n \bmod m \le |m|$?

Why isn't $n \bmod m \le |m|?$ I thought it holds for all integers, it seems to. But someone said that it has problems if $n < 0$ or $m < 0$.
mavavilj
  • 7,270
0
votes
2 answers

Find $a$ and $m$ for a given $x$ so that $ax≡1(mod(m))$

When the $\gcd(a,m)=1$, we know that $ax≡1\mod(m)$ does have an inverse in $m$. Normally $a$ and $m$ are given and $x$ must be found. How can I find $a$ and $m$ when only $x $ is given so that $ax≡1(\mod(m))$? For example when I choose $x=1337$ one…
766F6964
  • 113
  • 5
0
votes
1 answer

Rewrite ceil function of integer division

Say I have $\lceil \frac{a}{b} \rceil$, where both a and b are integers, is it possible to rewrite this? My intuition tells me that I can rewrite it as $\lfloor \frac{a}{b} \rfloor + (a\mod{b})$, but wolframalpha tells me no. However, wolframalpha…
0
votes
1 answer

In order to consider sign integer (both positive and negative) over some integer modulo space, should I use symmetric interval?

Can I use minus operation over mod 5, i.e. {0,1,2,3,4}?? If it was {-2 -1 0 1 2} I understand that works fine since we potentially have negative element.
mallea
  • 829
0
votes
1 answer

If $a \equiv b\;(\operatorname{mod} m )$ and $c \equiv d\;(\operatorname{mod} m ),$ prove that $a - kc \equiv 0\; (\operatorname{mod} m ).$

On my attempt : 1) $a \equiv b\;(\operatorname{mod} m )$ 2) $c \equiv d\;(\operatorname{mod} m )$ 2) Implies that $kc \equiv kd\;(\operatorname{mod} m )$ so $a-kc \equiv b-kd\;(\operatorname{mod} m ),$ and then I got stuck.
0
votes
1 answer

How to isolate $A$ in $A\%B=C$

How do I solve for a in the equation: $a\mod b= c\text{ (same as }a\%b=c$) Is there an inverse mod, so that I can put the equation in terms of a? Thanks in advance! b and c can be any real number I know that $a \mod b =a-\lfloor a/b\rfloor\cdot b$,…
0
votes
0 answers

Solving quadratic equations in Z/nZ

Is there a general methodology to solve $X^2 = X \:\mathbb{mod}\: n$? A solution verifies the interesting fact that $X^i = X \:\mathbb{mod}\: n$ for $i>0$. I think we can't really use discriminant like in algebra, but there may be a theorem…
0
votes
2 answers

Last two digits of n^n periodicity

Let $f(n) = n^n\:[100]$ be the euclidean remainder of $n$ to the power of itself divided by 100, also known as the last two digits in decimal notation. $n^n$ is a big number and time-consuming to compute. Is it true that f is 100-periodic? The…
0
votes
1 answer

modular arithmetic $ax=b$

I am familiar with finding solution to $ax=b$ in $\mathbb{Z_m}$ , but how could I know whether there is more than 1 solution? For example solving $83x=2$ in $\mathbb{Z_{321}}$ I have found $x=205$ but is there anymore? like in $2x=4$ where we get…
Rivaldo
  • 378
0
votes
2 answers

modular arithmetic proof question

I have to show that there are no integers x and y satisfying the equation 7$x^2-15y^2=1$. I don't know from where to start any hints. Thanks
Rivaldo
  • 378