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

Filter by
Sorted by
Tagged with
2
votes
1answer
471 views

Why does $q \equiv (r-1)/2 \mod r$ mean that $2q \equiv -1 \mod r$?

In the paper Safe Prime Generation with a Combined Sieve by Michael J. Wiener, the author states: For any small odd prime $r$, we can eliminate candidates for $q$ that are congruent to $(r − 1)/2\...
2
votes
1answer
3k views

How can I solve a vector equation in Z2?

I have a equation with 256 variables * 256-dimensional vectors in $\mathbb{Z}_2 $: $$ x_1 \cdot \left(\begin{array}{c} 1\\ 1\\ 1\\ \vdots\\ 0 \end{array}\right) + x_2 \cdot \left(\begin{array}...
1
vote
2answers
2k views

Non repeating random number generation with x(i+1) = x(i) + increment mod m

I have to generate millions of non-repeating random numbers and came across this equation: $x_{i+1} = x_i+c \space(mod \ m)$, where c and m are relative primes and $m \geq total\ to\ be\ generated$. ...
14
votes
2answers
751 views

Solve congruence: $45x \equiv 15 \pmod{78}$ (What am I doing wrong?)

Question about solving congruence. I've worked out how to solve them for the most part except for the following problem I'm having: $$45x \equiv 15 \pmod{78}$$ By the euclidean algorithm, I work out ...
6
votes
2answers
210 views

Efficient way to find $a$ in $c = 6a\mod n$

Given $c$ and $n$ in $c = 6a\mod n$, how can I find the lowest positive integer value for $a$? I could find it iteratively by rewriting as $\displaystyle a = \frac{c + xn}{6}$ and increasing $x$ ...
4
votes
6answers
3k views

How to find remainder modulo $n$, when $n$ is a large number

I am doing RSA questions and I really could use help! Can someone show me a simple way to find $25^9 \pmod{33}$?
3
votes
2answers
2k views

Generating sequences using the linear congruential generator

I came across the linear congruential generator on Wikipedia: http://en.wikipedia.org/wiki/Linear_congruential_generator I gather that for a particular choice of the modulus, multiplier and ...
0
votes
2answers
182 views

Help finding what prime numbers satisfy this condition

Given: ns_num(n, seed, modulo, incrementor) = (seed + n * incrementor) % modulo n is in range $[0,10000000)$ What value of ...
3
votes
2answers
2k views

How do I inverse a bijective modulo function?

In my discrete maths homework, I'm being asked to find the inverse of a cipher function: $$f(p) = (3p + 5) \bmod{26}$$ $f(p)$ accepts natural integers of the range ${0,1,...,25}$ (where A = $0$ and ...
5
votes
1answer
181 views

Primes for which $x^k\equiv n\pmod p$ is solvable: the fixed version

For fixed $n$ and $k$, how can I characterize the primes $p$ such that $x^k\equiv n\pmod p$? Less important to me: Is there a similar characterization for composite moduli? Assume the factorization ...
3
votes
2answers
180 views

Primes for which $x^k \equiv n \pmod{p}$ is solvable

For a fixed $n$, how can I characterize the primes $p$ such that there is a $k$ with $x^k\equiv n\pmod p$? Edit: This wasn't actually what I meant... the question I intended is here.
2
votes
2answers
86 views

Power equivalence in a prime modulus

Given, $p,q$ primes, $x$, $c$, $(p-1)/c$ integers and $$x^{(p-1)/c} \equiv 1\pmod{p}$$ how can I show there exists a $q$ such that $$q^c \equiv x\pmod{p}$$
4
votes
4answers
195 views

Find a number $b$ such that $a\cdot b\equiv 1\mod m$

Given two integers $a$ and $m$, such that $a\mathop\bot m,$ how can I find an integer $b$ such that $a\cdot b\equiv 1\mod m?$
1
vote
2answers
147 views

Moving powers in a prime modulus

Suppose I have $$x^{(c(p-1))} \equiv y^{(p-1)} \pmod{p}.$$ I would like to take the (p-1) root of both sides to get: $$x^c \equiv y \pmod{p}$$ I really just want to know if this a valid technique and ...
2
votes
1answer
638 views

Breaking RSA in a special case

This is a part of homework assignment, and I am stuck. The RSA signature is being calculated using Chinese Remainder theorem technique. Find the detailed description here. Public and private keys are ...
14
votes
2answers
2k views

nth powers modulo all primes

Let $a \in \mathbb{Z}$, $n \in \mathbb{N}^*$ be integers, and set $P=X^n - a$. Let us consider the three following statements : 1) $P$ has a root in $\mathbb{Z}$ (i.e. $a$ is an nth power) 2) $P$ ...
3
votes
4answers
14k views

Modulo arithmetic with big numbers?

I need to calculate $3781^{23947} \pmod{31847}$. Does anyone know how to do it? I can't do it with regular calculators since the numbers are too big. Is there any other easy solutions? Thanks
3
votes
1answer
354 views

What is the Voronoi's formula to calculate the inverse modulo m $ax \equiv 1 \pmod{m}$

I searched a bit using google but I found nothing :( ! Any information would be greatly appreciated. Thank you,
3
votes
1answer
21k views

fastest way to calculate the remainder (modular)

I'm creating a computer application in which I need to be able to calculate the remainder of large numbers (more then $30$ digits). I was searching the Internet for the fastest way to calculate this, ...
4
votes
3answers
439 views

Modular multiplication with machine word limitations

Imagine I have 64-bit machine and the widest integer available is 64-bit signed long. I cannot use BigInteger or similar libraries for performance reasons, and all calculations I get would me modulo $...
1
vote
2answers
97 views

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 ...
3
votes
2answers
6k views

Modular equations system

I have the following task - I have to find all a for which the following system has a solution: $x \equiv 1\pmod 2$ $x \equiv 2\pmod 3$ $x \equiv a\pmod 5$ I ...
2
votes
2answers
769 views

Number of solutions to a set of homogeneous equations modulo $p^k$

Let $p$ be a prime number and $k$ be a positive integer. How do I determine the number of solutions to a set of equations in variables $0\leq x_1,...,x_n<p^k$? All equations are of the form $\...
1
vote
0answers
105 views

Find $x$ satisfying $x^a\ \textrm{mod}\ b \geq c$ where $a$, $b$, and $c$ are known

If $a$, $b$, and $c$ are known, is there an efficient way to find values of $x$ which satisfy $x^a\ \textrm{mod}\ b \geq c$ ?
2
votes
1answer
542 views

Prove that: (a * b)$^{x}$ mod n = ((a$^{x}$ mod n) * (b$^{x}$ mod n)) mod n

(a * b)$^{x}$ mod n = ((a$^{x}$ mod n) * (b$^{x}$ mod n)) mod n Can anyone give me some tips to prove the above equation? Thanks.
0
votes
2answers
179 views

Finding x in $a^{x} \bmod b = c$ when values a,b, and c are known?

If values $a$, $b$, and $c$ are known, is there an efficient way to find $x$ in the equation: $a^{x} \bmod b = c$? E.g. finding $x$ in $128^{x}\bmod 209 = 39$.
2
votes
1answer
1k views

Modular Inverse using Extended Euclidean Algorithm

I am trying to find the modular inverse for $(n+1)\pmod {n^2}$ using EEA and I end up getting $1-n$ as the modular inverse. But, I want the inverse to be a positive number since its modular arithmetic....
2
votes
2answers
115 views

Prove that $(n-1) = (n - 1)^{\beta} \pmod{n}$ when $n$ is even

Let $\alpha$, $1 \lt \alpha \lt \varphi(n)$, $\gcd(\alpha, \varphi(n)) = 1$, and $\beta \equiv \alpha^{-1} \pmod {\varphi(n)}$, where $\varphi$ is Euler's totient function. When n is even, how would ...
1
vote
1answer
157 views

Prove $(n -1) = (n-1)^{n}$ mod n

Prove $(n -1) = (n-1)^{n}$ mod n How would one go about doing this?
12
votes
2answers
3k views

The modular curve X(N)

I have a question about the modular curve X(N), which classifies elliptic curves with full level N structure. (A level N structure of an elliptic curve E is an isomorphism from $Z/NZ \times Z/NZ$ to ...
3
votes
2answers
9k views

modular arithmetic, solving $ax + b \equiv c \pmod d$?

For example $151x - 294\equiv 44\pmod 7 $. How would I go about solving that? The answer says to simplify it into the $ax\equiv b\pmod c $ form first, but I have no clue on how to get rid of the $294$...
6
votes
1answer
133 views

Which functions satisfy $\forall n,x,y (x \equiv y \pmod n \implies f(x) \equiv f(y) \pmod n )$?

Which functions satisfy $\forall n,x,y (x \equiv y \pmod n \implies f(x) \equiv f(y) \pmod n )$ ? I know polynomials do; are there others?
1
vote
1answer
198 views

Modular Arithmetic [duplicate]

Possible Duplicate: Modulo Arithmetic How would you find x in a modulo arithmetic expression x^e mod p knowing only e and p? e is an integer, 0 ≤ e < p, that is relatively prime to p-1; and x ...
0
votes
2answers
249 views

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 ...
1
vote
6answers
17k views

Calculator model with mod function?

I'm wondering does anyone know of a scientific calculator with a mod function? In C# this is shown as follows (just in case there are any other mods that a mathematical non-savant such as myself ...
2
votes
1answer
1k views

Prove that a given sequence is periodic modulo m

How can one tell that a given sequence is perodic modulo m? For example its easy to see that the sequence $1^1, 2^2, 3^3, \dots$ is periodic modulo 10. But how can we prove this?
2
votes
2answers
231 views

Perfect square. Factorising problem

What is the sum of all positive integers $n$ for which $2^n + 65$ is a perfect square?
3
votes
3answers
1k views

Solve $f(x) = 6x^3 + 27x^2 + 17x + 20 \equiv 0 \pmod{30}$

Problem Solve $f(x) = 6x^3 + 27x^2 + 17x + 20 \equiv 0 \pmod{30}$ My attempt was: Since $30 = 2.3.5$, we then have: $$ \begin{cases} f(x) \equiv 0 \pmod{2}\\ f(x) \equiv 0 \pmod{3}\\ f(x) \...
1
vote
4answers
368 views

Question regarding solving polynomial of congruence?

In my textbook, they said: $$2x^{3} + 7x - 4 \equiv 0 \pmod{5}$$ The solution of this equation are the integers with $x \equiv 1 \pmod{5}$, as can be seen by testing $x = 0, 1, 2, 3,$ and $4.$ And ...
2
votes
2answers
1k views

How to prove Lucas's Converse of Fermat's Little Theorem without using primitive root?

Problem: If $x^{n-1} \equiv 1 \pmod{n}$, and for all divisors $q$ of $n - 1$, $a^{q} \not\equiv 1 \pmod{n}$, then $n$ is prime. $(n > 1)$ I read the proof in the book and it was very ...
8
votes
3answers
4k views

Show that if $a \equiv b \pmod n$, $\gcd(a,n)=\gcd(b,n)$

My problem is how to somehow relate the the gcd and congruence. I know that $(a,b) = ax + by$. I also know that $a \equiv b \pmod n$ means $n\mid a-b$. Any hints? Thanks!
60
votes
7answers
146k views

How to find the inverse modulo m?

For example: $$7x \equiv 1 \pmod{31} $$ In this example, the modular inverse of $7$ with respect to $31$ is $9$. How can we find out that $9$? What are the steps that I need to do? Update If I have ...
3
votes
3answers
927 views

Efficient way to find $a^b \bmod {n}$

I am not sure whether or not this is a duplicate question. I'm wondering what is an efficient way to compute $$x \equiv a^b \bmod{n}$$ where $a,b,n \in \mathbb{Z}$ and $a,b < n$? For example say I ...
1
vote
4answers
1k views

Multiplicative Inverse and RSA

I have been going through the RSA cipher and have been wondering if there is a way other than the Extended Euclid Method to find $a^{-1} \mod n$ where a,n $\in$ Z P.S : n is not necessarily prime
2
votes
2answers
160 views

Modular numbers

I just learned about modular numbers on wikipedia, such as $17 \equiv 3\pmod{7}$. So what is infinity $\pmod{n}$? It can't very well be all the numbers at once, so what happens?
6
votes
7answers
2k views

Show that $3^{4n+2} + 1$ is divisible by $10$

I'm am a little bit stuck on this question, any help is appreciated. Show that for every $n\in\mathbb{N}$, $3^{4n+2} + 1$ is divisible by $10$.
2
votes
1answer
110 views

Solving $N\equiv1\pmod2,N\equiv2\pmod3,\dots,N\equiv n-1\pmod n$

If I have: \begin{align*} N &\equiv 1 &\pmod{2}\\ N &\equiv 2 &\pmod{3}\\ N &\equiv 3 &\pmod{4}\\ &\vdots\\ N &\equiv n - 1 &\pmod{n} \end{align*} How could I ...
1
vote
1answer
108 views

A congruence in a quadratic number field

If $\displaystyle L = \frac{3+\sqrt{-3}}{2}$, and if $x\equiv 1\pmod{L}$, show that $x^3\equiv 1\pmod{L^4}$. I have already shown that if $x\equiv 1\pmod{L}$, then $x^3\equiv 1\pmod{L^3}$. ...
1
vote
3answers
3k views

How to find the last digit of $3^{1000}$?

I'm thinking of modulo, but really don't know how to start? A hint would be sufficient. Thanks, Chan