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

1
vote
1answer
25 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
0answers
30 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
45 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
48 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
26 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
0answers
25 views

Modular multiplicative inverse problem.

I am trying to find the inverse of 314(mod 7). I have no idea what I am doing wrong.. What I do is: 1) find if gcd(314,7) = 1. Yes! 314 = 7*44 + 6 7 = 6*1 + 1 6 = 1*6 + 0 2) Now to find ...
-4
votes
1answer
39 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
52 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
30 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
20 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
29 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
219 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
37 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
25 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
42 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
33 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
18 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 ...
0
votes
0answers
17 views

Polynomial Reduction Modulo p

Here goes a stupid question... It's well known that a polynomial $f\in \mathbb{Z}[X]$ is irreducible if it is irreducible modulo $p$ for some prime $p$. This is since if $f=gh$ then this will still ...
2
votes
5answers
48 views

How to solve large modulus manually? [closed]

given $52^{35}\mod 85$ I know I can change that to $52\cdot 52^{2^{16}}\mod 85$ but I'm unsure where to go from there.
2
votes
4answers
41 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
43 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
31 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
19 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?
0
votes
0answers
65 views

Rsa encryption/decryption (Updated)

1. Show that Bob can efficiently compute the encryption C(m) of the message m that he wants to send to Alice, knowing the public key but not the private key. Note: here (as well as in the rest of ...
3
votes
4answers
79 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
19 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
52 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
15 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 ...
1
vote
1answer
24 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 ...
0
votes
0answers
50 views

Showing that 2^(N-1) is equivalent to 1 mod N [closed]

My math professor gave us the following problem on a past exam and I didn't get it right then and I still don't know how do it: ...
1
vote
1answer
37 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
32 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
52 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
21 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 ...
0
votes
1answer
17 views

Method to solve for a number in modulus equation.

If you had an equation of 12 = (8000 + B) mod 13 You could guess and check a little and arrive at B = 7. My question is what is the best way to solve these? Is there a defined method to get B?
0
votes
1answer
21 views

polynomial modulo polynomial

If $h(x) = x^2 + 1$, $g(x) = x^2 + x + 1$ and $f(x) = x^3 + x + 1$, then $$ \begin{align} g(x)h(x) \mod f(x) &\equiv (x^2 + x + 1)(x^2 +1) \mod x^3 + x + 1 \\ &\equiv x^4 + x^3 + 2x^2 + x + ...
1
vote
1answer
23 views

Secret sharing: modular arithmetic

I have this problem of sharing a secret code $n\in\mathbb{Z}$ such that $0\le n\le250$ among five people. There are 5 people, each one of whom receives a secret number $s_i$, $1\le i\le 5$ such that ...
0
votes
1answer
30 views

Solving a quadratic congruence (mod p).

Solve $x^2 \equiv 6 (mod~97)$. There is an algorithm in my book. Initialization: I1: Determine the integers $k,m$ such that $p-1= m \cdot 2^k$, where $k \geq 1$ and m is odd. Then $97 - 1 = 3 ...
0
votes
2answers
29 views

Combining GCD and congruences

Let $a, b, m, k \in \Bbb Z$ such that $m\ge2$ and $k\not=0$. Let $d=\gcd(k,m)$. Prove that if $a\equiv b\pmod m$ and $k$ is a common divisor of $a$ and $b$, then ${\frac ak}\equiv {\frac bk}\pmod ...
0
votes
1answer
36 views

Proofing the existence of a non-zero congruence class

Let $m\ge2$ be an integer. Show that if there is an integer $a$ such that $\gcd(a,m)=d\not=1$, then there exists a non-zero congruence class $[x]$ in $\mathbb{Z}_m$, such that $[a]\cdot[x]=[0]$. I ...
2
votes
3answers
42 views

Solve $9x$ $\equiv 4 \mod1453$

In Underwood Dudley's Number theory book second edition chapter 5 problem 7 I encountered this problem: Solve $9x\equiv 4 \mod1453$ I know that since $gcd(9,1453)=1$, there exists a unique solution. ...
0
votes
0answers
12 views

Will XORing any data with random data produce a random result?

Provided you have a stream of input data and a stream of random data both in the set (0,1). The random is data truly random, that is, unpredictable by the user and ...
0
votes
2answers
24 views

Rules for Calculating Modulo

I have two questions about using modulation in equations. My first question is what notation is the right to use (i.e. x%y or mod(x, y))? The second is what are its properties for adding, multiplying, ...
0
votes
1answer
44 views

Generator of $Z_p^*$ with large p

I have to find a generator for $Z_{p}^*$. The prime number p is $2425967623052370772757633156976982469681$. My prime factors for (p-1) is according to 1 ...
0
votes
1answer
28 views

Showing that the linear twist map is sensitive dependent

Choose $\Delta=\frac{1}{2}$ (I believe this value should work). let $\delta > 0$ and let $\textbf{x}_1=(x_1,y_1) \in X$. I assuming that $d$ is the Euclidean distance. Somehow I think we ...
1
vote
3answers
62 views

Finding remainders using modulo

Determine the remainder of $2014^{2015} \cdot 2016^{2017} + 2018^{2019}$ divided by 13. I can't figure out how to manipulate the 2018 part to get it to some form of 13. Any suggestions?
1
vote
0answers
22 views

Question about a particular case of the sum of three squares.

I was recently given a math problem by a friend; the challenge was to find a rectangular prism whose side lengths (including diagonals and space diagonal) were all natural numbers. I found that for ...
0
votes
1answer
33 views

Solving a system of modular power congruences

I have to find the $x$ value such that $x^k \equiv a_1 \pmod n$ and $x^q \equiv a_2 \pmod n$, where $k$, $q$, $a_1$, $a_2$ are known constants and $n$ is any number. Is there a method to find $x$ ...
0
votes
3answers
28 views

Multiplicative inverse

What is the multiplicative inverse of 7 modulo 11? Is this correct: $$7 = 11(0) +7$$ $$11 = 7(1) +4$$ $$7 = 4(1) +3$$ $$4 = 3(1) +1$$ We then take 3 equations: $$4 = 11 + 7(-1)$$ $$3 = 7 + 4(-1)$$ ...
0
votes
2answers
32 views

Factorization and modular inverses

In this post in the last method the factorials were factorized. But I don't quite understand how that works. Lets say we have $$ (-24)^{-1}+(6)^{-1} +(-2)^{-1}$$ modulo a prime $p$, for instance ...