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 $b-a$.

learn more… | top users | synonyms

2
votes
1answer
54 views

Relation between $(a\bmod b)\bmod c$ and $a\bmod c$

Will (a%b)%c be equivalent to a%c? Given $b>c$ and $b$ is a prime number? If not is there any other equality that will hold? ...
0
votes
1answer
44 views

How to find $a\mod N $ in a specific way?

Let's I have an integer a and take it's modulo with M (M is a prime Number) which is b. i.e. $b = {a\mod M}$I would like to get $a \mod N$ by doing some operation on operation on b along with M , ...
0
votes
1answer
14 views

How do you create an operation for circular indices of a vector?

So I am trying to construct a way to find the next X letters (using the ASCII codes). But it is circular such that the next letter after Z is A. So Z+1 would be A. So basically it is an array (or ...
0
votes
2answers
33 views

Operations on congruence equations?

I have to do back substitution for my homework, and I have to modify x ≡ 1 (mod 5) to x=5t+1, which I understand. What I don't understand is when I put this into the next equation which becomes 5t + 1 ...
1
vote
1answer
151 views

question about cryptography

Sam and Tim have set up their RSA keys (eS; n); (eT; n), respectively, where the n-value is the same. Furthermore, it happens that gcd(eS;eT) = 1. Suppose that their friend Rob wants to send both Sam ...
0
votes
1answer
95 views

Euclid's proof for infinitely many prime numbers

Prove that there are infinitely many primes congruent to 3mod4 using euclid's proof for infinitely many prime number. I guess I don't really know where to start because I don't understand euclid's ...
1
vote
1answer
28 views

How do you compute $\frac{p}{qrs} \mod M$?

I would like to find $\frac{p}{q\space \space\space r\space \space s} \mod M $ . As multiplication of denominator can become large .So , $\frac{p}{q\space \space\space r\space \space s} \mod M $ = ...
4
votes
1answer
85 views

$a^2+ab+b^2 \equiv 0 \pmod n$ if and only if $ a\equiv b\equiv 0 \pmod n$

Let $n$ be a prime number with $n \equiv -1 \mod 6$ and $a,b$ be positive integers. I want to prove: $$a^2+ab+b^2 \equiv 0 \mod n \iff a\equiv b\equiv 0 \mod n$$
2
votes
1answer
1k views

How to deal with negative exponents in modular arithmetic?

So I think I understand how to calculate something like $(208\cdot 2^{-1})\mod 421$ using extended euclidean algorithm. But how would you calculate something like $(208\cdot2^{-21})\mod 421$? ...
0
votes
1answer
63 views

Modular Division For non co-prime numbers

How can I calculate $(x*k)/i$ (mod $m$) where i and m are relatively not co-prime ? We know that, if $\gcd(i,m)\neq1$ , then there doesn't exist a modular multiplicative inverse of $i$ mod $m$. Then ...
1
vote
2answers
131 views

Fun results from modular arithmetic

I'm trying to go through various bits of neat, fun math with some junior-high-school students in my local area, and am thinking of doing a short unit on modular arithmetic/finite groups. I'm looking ...
0
votes
1answer
37 views

How to compute n(mod c) when n(mod a),n(mod b),a,b,c are given?

Given a(prime) > b (prime) > c(any number), is there any way to compute n(mod c) ? n%a,n%b,a,b,c are known.
1
vote
1answer
33 views

Quadratic nonresidues mod p

The question asks to find congruence conditions on prime $p$ such that $7$ is the least quadratic nonresidue mod p. Also, find the least such prime. I solved it for $1,2,3,4,5,6$ mod $p$ and got ...
0
votes
2answers
65 views

Show there is no solution to this equation

I have to show that $2x^4-20x+8$ cannot be divided by $16$ without remainder. The only thing comes to my mind is to write $16$ as $4^2$ which hasn't been of any help. Could you give me some hints to ...
1
vote
6answers
1k views

simple 'why' question about modular arithmetic 13 mod 5

After checking out khan academy "what is modular arithmetic" https://www.khanacademy.org/computing/computer-science/cryptography/modarithmetic/a/what-is-modular-arithmetic they say that 13/5 = 2 ...
0
votes
1answer
59 views

Euclidean Algorithm / arithmetic mod question

I'm not sure how to approach this problem: Solve for $x$. $788x \equiv 24 (mod 1647)$. I know that if 24 were replaced with 1, I could just do a backwards euclidean algorithm to find x. Can I still ...
0
votes
2answers
44 views

What steps are needed to solve $5x+80 = 13 \pmod 7$ and similar problems?

I am unsure of the steps needed to solve $$5x+80 = 13 \pmod 7$$ or this, $$31x=2\pmod{19}$$ I would like to see the steps necessary.
-1
votes
1answer
116 views

Hexadecimal vs. Mod 16

Why is it that hexadecimal has both F and 0 when F is the 16th character in the sequence? Why is the same true of decimal notation? Doesn't this mean it is not compatible with modular arithmetic ...
3
votes
2answers
19 views

Congruence equation for modulus 2

Suppose $a,b\in\mathbb{Z}$ and $n\in \mathbb{N}$. Is the equation $$((a+n)(b+n)) mod_2 = ((a-n)(b-n)) mod_2$$ satisfied? This is not a homework or such. (I'm not a student) I need to decide if two ...
1
vote
1answer
71 views

Method to solve quadratic congruence

I learned quadratic congruence by myself and stuck in these problems: I know if quadratic congruence $X^2=a(\mod\mbox{ p} )$ with $p$ is an odd prime number and $\gcd(a,p)=1$, then it has no ...
1
vote
1answer
71 views

Solving $\frac{x}{y}$ mod $m$ efficiently?

We know that : $( x.y )$ mod $m$ = ( ($x$ mod $m$) . ($y$ mod $m$) ) mod $m$ Is there any property for: $\frac{x}{y}$ mod $m$ like $\frac{x \mod m}{y \mod m}$ mod $m$ . I hope this fails. I want to ...
1
vote
0answers
59 views

A variant of factorial

Given the definition of a function f as f(n)=1^1 * 2^2 * 3^3 * ... * (n-1)^(n-1) * n^n. Another function g is defined as g(n,r)=f(n)/(f(r)*f(n-r)) Given an n,r,m we are to output g(n,r)%m where m is ...
0
votes
2answers
98 views

modulo of a large number

I need help with solving modulo of large numbers, wondering if it is possible to compute the answer without the use of calculator. for example: 545^112 (mod 23) how can this be solved? I reduced my ...
0
votes
1answer
51 views

Creating modulo formula to convert numbers

I need a formula that makes the following conversion from a to b: a b 0 -> 2 1 -> 3 2 -> 4 3 -> 5 4 -> 6 5 -> 7 6 -> 1 By trial and ...
0
votes
3answers
89 views

Product of two odd numbers is odd

How do I prove that the product of odd integers is odd? I know that I'm supposed to use an algebraic equation.
-3
votes
1answer
57 views

how to do the opposite of mod in this equation

if $X=((A*Y)+C)\mod m$ how does one calculate $Y$? If you have all other variables except Y? I have already tried everything I can think of just don't know how to do the exact opposite of mod, I can ...
1
vote
1answer
163 views

Solve Inverse Linear Congruence

I want to solve Linear congrunece : 9x+2 ≡ 6(mod 1453) using inverse of 9 mod 1453. Inverse of 9 mod 1453 is 323. Now to solve it I subtract 2 from left and right side which gives me 9x ≡ 4(mod 1453), ...
0
votes
1answer
104 views

Solve quadratic equations modulo prime powers

To find if $x^2 = a \mod p$, I use the Tonelli-Shanks algorithm. However, how do I find the roots for $x^2 = a \mod p^t$, if I have solved the previous equation? Thanks
2
votes
1answer
26 views

Setting 2 equations equal in modular arithmetic

Let us say that I have some m, say $5z+25$ (where $z$ is some random integer), and $n$ is say $3z+9$ (same $z$). I want to find an equation that correlates $m$ and $n$ in some $\text{mod} \,O$. ...
1
vote
1answer
69 views

Conclude that the multiplicative order modulo $ab$ of any $c$, $gcd(c,ab) = 1$ must be a proper divisor of $\phi(ab)$.

a) Show that if $n = ab$ where $1 < a, b$ are odd and $gcd(a,b) = 1$, then $lcm(\phi(a),\phi(b)) < \phi(ab)$. b) Conclude that the multiplicative order modulo $ab$ of any $c$, ...
7
votes
1answer
230 views

Reference request for unknown mathematical constant

Below is a plot of $$\dfrac{1}{x}\sum_{n=1}^{x}x\ (\mathbb{mod}\ n)-\dfrac{x}{5.6325}$$ where $5.6325$ is very close to whatever the constant actually is. Does anyone know what this constant ...
0
votes
2answers
206 views

How to handle negative numbers in modular arithmetic?

I have a constraint to use finite-field arithmetic in my application. Since I want it to resemble ordinary arithmetic as much as possible, I chose a large prime $p$ (e.g., $ p > 2^{256} )$, and I'm ...
0
votes
1answer
45 views

Remainder addition

Here is the problem. We are given two numbers, a and m. We have to print if at some point 'a' will be divisible by 'm' or it will get stuck in a loop. If a % m is not divisible then new value of a ...
0
votes
2answers
59 views

Are the solutions of $x^2 = -y^2 \mod n$ always based off of $x^2 = -1 \mod n$

We know that if $x_i^2 = -1 \mod n$ we are able to find more solutions of the form, $x^2 = -y^2 \mod n$ Simple Proof: Let $x_i$ be the initial solution to $x_i^2+1 \equiv 0 \mod n$ ...
0
votes
1answer
132 views

Minimum number of Roots of a Polynomial Modulo n

Consider over Z/nZ $$ x^2+x = 0 $$ (a) Find an n such that the equation has at least 4 solutions. (b) Find an n such that the equation has at least 8 solutions. Could someone help me out here? I'm ...
0
votes
1answer
33 views

Difficulty understanding the solution to a problem.

I am studying a book right now, and I'm having a difficulty understanding a (solved) problem regarding congruent modulo. Below I will list the problem and what I have understood of the problem, along ...
3
votes
1answer
115 views

Why doesn't the equation have a solution in $\mathbb{Q}_2$?

I have to find for which primes $p$, the equation $x^2+y^2=3z^2$ has a rational point in $\mathbb{Q}_p$. According to my notes: Obviously, $\forall p \in \mathbb{P}, p \nmid 2 \cdot 3$, there is a ...
2
votes
4answers
52 views

Solving equations with mod

So, I'm trying to solve the following equation using regular algebra, and I don't think I'm doing it right: $3x+5 = \pmod {11}$ I know the result is $x = 6$, but when I do regular algebra like the ...
1
vote
3answers
52 views

Question on modulo

Find the last two digits of $3^{2002}$. How should I approach this question using modulo? I obtained 09 as my answer however the given answer was 43. My method was as follows: $2002\:=\:8\cdot ...
2
votes
1answer
137 views

Modular Cubic Formula

What would be the process of solving a modular cubic equation? Eg. $$ax^3+bx^2+cx+d=0\pmod n$$ In the case that I was given, $d$ is a (very) large number, so rational root theorem isn't a viable ...
1
vote
1answer
52 views

Solve for exponent in modular exponentiation

If given that N^x mod C = B How does one solve for x if (x > 1). I did CRT and got 1, so does anyone know what direction I should go?
3
votes
4answers
205 views

How to compute $3^{2003}\pmod {99}$ by hand? [duplicate]

Compute $3^{2003}\pmod {99}$ by hand? It can be computed easily by evaluating $3^{2003}$, but it sounds stupid. Is there a way to compute it by hand?
1
vote
1answer
49 views

Solving for x (Modular Arithmetic)

Solving systems of equations with Modular Arithmetic can be complex, especially with the following equations: $$(a_0x+{a_0}^2)^e \equiv C_0\;(mod\;n)$$ $$(a_1x+{a_1}^2)^e \equiv C_1\;(mod\;n)$$ My ...
0
votes
3answers
79 views

How to solve $100^{63}$ mod 63

I am trying to solve this question but not able to figure out how to approach it. $100^{63} \mod\ {63}$ Please help.
1
vote
1answer
24 views

Simple Modular Arithematic with Negative Numbers

If given an equation in the form: 3 = x mod 13 I know that I can generate a solution set by doing: X = 13q + 3 And ...
2
votes
1answer
50 views

Quadratic modulus

What is a fast way of finding a solution M to a quadratic modulus of the form a == M (M + b) mod n where a and n are very large, and b << a n is the ...
1
vote
1answer
46 views

Equation $x^2 + y^2 + 1 = 0$ (mod $p$)

How to prove that equation $x^2 + y^2 + 1 = 0$ (mod $p$) has roots? Hints are acceptable.
0
votes
1answer
33 views

Two questions concerning divisibility

I was looking at some proof questions and had difficulty answering a few of them How do I prove these statements below: 1) $3 \mid (10^{n+1} + 10^n + 1)$ 2) $(a-b) \mid (a^n - b^n)$
1
vote
1answer
91 views

How to compute: $(89^{3} \bmod 79)^4\bmod 26$?

How to compute: $(89^{3} \bmod 79)^4\bmod 26$?? It's easy to calculate it by evaluating $89^{3}$ first and then mod $79$, but it seems stupid to do it this way. Do we have a faster way to evaluate ...
0
votes
1answer
26 views

If $a\equiv 4\pmod {13}$, a is integer, Find c ($0 \leq c \leq 12$) so that $c\equiv 9a\pmod {13}$

If $a\equiv 4\pmod {13}$, a is integer, Find c ($0 \leq c \leq 12$) so that $c\equiv 9a\pmod {13}$. I translated these into the form of definition: 13 | a-4 and 13|c-9a, then I got stuck on it. I ...