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
3answers
12 views

How one can deduce that $tx≡2t[mod(z)]$?

Let $x,y,z,t$ four positive integers. If $$x≡2[mod(y)]$$ and $$z=ty$$ Then how one can deduce that $$tx≡2t[mod(z)]$$
11
votes
1answer
200 views

Solving $n^5+n^4-3=x^2\pmod p$

Prove that for every odd prime number $p$ there is a natural number $n$ such that the equation $n^5+n^4-3=x^2\pmod p$ has no solutions. So we have to understand that for each $p$ we can find $n$ ...
-1
votes
0answers
20 views

Prove divisibility - modular arithmetic

Could anyone help me solve this $For p\in prime, p>3, let$ $a=(p-1)![1+1/2+...+1/(p-1)]\in N $ Then prove that p|a and also $ p^2|a$ Thanks in advance!
0
votes
0answers
67 views

How can I check these equations if they have a solution?

I have two equations which are: $p^3+k\equiv0 (mod \quad h) $ and $(3p^2+3mp+m^2)m\equiv 0(mod \quad h)$ where $k,h,m >0$ and $p\ge0$ and $h\nmid m$ I need to show for given k,m,h and for all ...
0
votes
1answer
34 views

Compute the product of digits of P

Give $P$ a integer number where $$P=2^{3^{4^{5^{\dots1000}}}}$$ Then Compute The product of dígits of $P$ Compute $P\pmod{5}$ for The segond i think its will be something like ...
3
votes
1answer
28 views

Modular arithmetic with huge modulus?

When the dividend is some huge power but the modulus is not so big, I can use modular exponentiation. But how can I compute the residue when the modulus is, for example, $2^{107} - 1$, a Mersenne ...
2
votes
1answer
28 views

Given some large integer, is there way to construct a modulus such that the remainder that is below some threshold?

The proper context is integers too large for factorization to be computationally feasible, but, for the sake of illustration, the question is given an integer, such as 228483159, is there a procedure ...
2
votes
2answers
35 views

In Zagier's one-sentence proof, why is S defined to be {(x,y,z)∈ℕ^3:x^2+4yz=p,p prime}?

I've looked at a very clear explanation of Zagier's proof (specifically, it can be found here:http://danielmath.wordpress.com/2012/12/26/one-sentence-proof/) but the first step still eludes me: why is ...
1
vote
2answers
50 views

How to solve $x^2 \equiv [1]$ in $\Bbb Z_5$

I would like to know how to solve $x^2 \equiv [1]\text{ in }\Bbb Z_5$? How to solve this kind of equation in general?
2
votes
1answer
18 views

Inverses modulo a prime power

My question relates to inverses modulo $p^k$ for prime $p$. I came across an article that gave a recurrence relation for computing inverses modulo $p^{2^n}$, but it did not make clear how (or even ...
1
vote
0answers
31 views

Modulo Square Roots [migrated]

Here's my issue and someone can help me understand it so I can program it correctly. I have a point(X,Y) on an Elliptical Curve E(a,b) where a=-3 and B is a large number that is in hexidecimal from ...
3
votes
2answers
50 views

The inverse of $4$ modulo $9$

Can someone explain why the inverse $4$ modulo $9$ is $7$? What am I missing? $$9 = 2\cdot4 + 1$$ $$1 = 9-4\cdot2$$ $$1 = -2\cdot4 + 1\cdot9$$ Isn't then $-2$ inverse of $4$ modulo $9$?
1
vote
1answer
26 views

Elliptic curves: Can I replace a coordinate with any modularly equivalent number?

I have a point (x, y) in an elliptic curve group. Suppose y is negative. Can I rewrite it as a positive number if that positive number is equivalent to y (modulo the characteristic of the group)? ...
0
votes
1answer
21 views

El Gamal encryption/decryption

First of all I want to ask if I did part a correctly? Alice has two secrets, $s_1 = 55$ and $s_2 = 108$ and wants to communicate one of them to Bob without knowing which one. Alice and Bob agree to ...
2
votes
2answers
46 views

Principal Square Roots Mod

Suppose you know the factorization $8509 = 67\times127$. (a) Use this to compute the principal square roots of $98^2$, $99^2$, $100^2$, and $101^2$, modulo $8509$. I thought that I find the ...
2
votes
0answers
33 views

Size of increments in commutative ring to reach given number

I have the ring $\Bbb Z_q = \{0,1,\ldots,q-1\}$, where $q$ is a prime. Starting from $0$, I want to make exactly $n$ equally sized increments and reach $a\in \Bbb Z_q$, with $n<q-1$. For example if ...
0
votes
0answers
29 views

How to solve $3r_2-2r_3 \equiv 0 \mod{6}$?

Is there a general method to find all solutions to equations like the following: $3r_2-2r_3 \equiv 0 \mod{6}$ where $r_2$ is the remainder after division of 2 i.e. $r_2 \in \{0,1\}$. ...
1
vote
1answer
32 views

Proof that $(k+m)^2 \mod{n}$ is not injective [closed]

$M=K=C=\mathbb{Z}_n$ Lets say $n=10$ $E(k,m) = (k+m)^2 \mod{n}$ Proof that E is not injective (over $\mathbb{Z}_n$) for any key $k \in K$. So what this means, is that any $n$ consecutive squares ...
0
votes
2answers
30 views

Show that $p$ must be congruent to either 1 or 4 modulo 5

Let $p$ be a prime number $(p \neq 2$ and $p \neq5)$, and let $A$ be some given number. Suppose that $p$ divides the number $A^2 - 5$. Show that $p$ must be congruent to either 1 or 4 modulo 5. A ...
2
votes
1answer
39 views

Does the congruence $x^2 - 3x - 1 \equiv 0$ (mod 31957) have any solutions?

Does the congruence $x^2 - 3x - 1 \equiv 0$ (mod 31957) have any solutions? (A hint given is that I can use the quadratic formula to find out what number you need to take the square root of modulo ...
0
votes
3answers
61 views

Prove the existence of non trivial solution

The question is Prove that if an odd integer n > 1 is not a prime or a prime power, then there exists a nontrivial square root of 1 modulo n. There is a proof "If n is composite, then there exists ...
2
votes
2answers
113 views

Proving $(a+b)^{p} \equiv a^{p} + b^{p} \pmod{p}$ for prime $p$ [closed]

I am having trouble proving that any prime number $p$ and integers $a$ and $b$, $(a+b)^{p} \equiv a^{p} + b^{p} \pmod{p}$
1
vote
0answers
32 views

Consistent hashing using modulo

Following my answer here: Suppose I have n servers, and I want to distribute files evenly between them (same number of files on each server). Initially n=2 and I use the following function to map a ...
1
vote
1answer
46 views

How to prove integers has a cubic root mod p?

Using p ≡ -1 (mod 3) and p is prime, how can you show $a^3≡b$ (mod p) iff $a≡b^d$ (mod p)? This shows integers mod p has a unique cubic root. 3d ≡ 1 (mod p-1) I'm not sure where to begin... Does ...
0
votes
0answers
21 views

How to compute addition on eliptic curve mod p?

I have a point P=(10, 9) on the curve $y^2 ≡ x^3 + 26$ mod(35) and I am trying to calculate 3P. I know that for when you do P3 = P1+P2 and P1!=P2, you can do $m=\frac{y_2-y_1}{x_2-x_1}$ $x_3 = m^2 ...
0
votes
2answers
17 views

Raised to the power and modulus

Task: $26^{61}(\pmod {851}$ And I stucked with the operation pow(26,61) because it's too hard for me. I read the article about this problem, but I don't quite understand how to solve it. I can ...
0
votes
2answers
19 views

RSA and find 'd'

So, my task is to find d if $p=5, q=11, e=17$. Here I've tried: Find $n=p\cdot q = 5*11 = 55$ Find $\phi(n) = (p-1)(q-1)=(5-1)(11-1) = 40$ Euclidean algorithm: $$ 40=2\cdot 17+6 \\ 17 = 2\cdot 6 + 5 ...
0
votes
1answer
25 views

residue classes and group-theory

I have a question about how I have to do these exercises for my math study Let $n \in \mathbb{Z}, n>0$ and $a \in Z$ a) prove: if $n$ is odd, then $\overline{a} = \overline{(-a)}$ if and only if ...
0
votes
1answer
21 views

Could there be infinite solutions to a modular linear equation?

Could there be infinite solutions to a modular linear equation of the form Ax = b mod n when solving for x?
0
votes
2answers
49 views

Proof of a series of congruences

Prove that this is impossible: $$ \begin{cases} a_2 a_1 \equiv a_1 \pmod{n}\\ a_3 a_2 \equiv a_2 \pmod{n} \\ a_4a_3 \equiv a_3 \pmod{n} \\ \ldots\\ a_1a_k \equiv a_k \pmod{n} \end{cases}$$ For any ...
0
votes
2answers
43 views

How do I solve simultaneous congruence modulo equations

How do I find one value of $x$ in these equations? $$ \begin{cases} x \equiv 3 \pmod{5}\\ x \equiv 4 \pmod{7} \end{cases} $$
0
votes
0answers
27 views

What is the correct term (and symbolic representation) for specific “un-modded” values?

Given $x \in \mathbb{R}$ such that $x \equiv x+k\cdot(b_u-b_l),\,\forall k\in\mathbb{Z}$, are there terms to describe the functions $$f:[b_l, b_u) \to[b_u, b_u+(b_u-b_l)):x\mapsto x+(b_u-b_l)$$ and ...
0
votes
3answers
42 views

Modulo: Calculating without calculator??

Calculate the modulo operations given below (without the usage of a calculator): $101 \times 98 \mod 17 =$ $7^5 \mod 15 =$ $12^8 \mod 7 =$ $3524 \mod 63 =$ $−3524 \mod 63 =$ Ok with calculator ...
0
votes
1answer
10 views

System modular equation. Question.

$$2x \equiv 4 \mod 8 \iff x \equiv 2 \mod 4 $$ And this is true, but is it a true?: $$\begin{cases} 2x \equiv 4 \mod 8 \\ x \equiv 2 \mod 6 \end{cases} $$ $$\iff$$ \begin{cases} x \equiv 2 \mod 4\\ ...
1
vote
6answers
62 views

How to solve this equation if we can't use Chinese remainder theorem.

Let consider: $$\begin{cases}6x \equiv 2 \mod 8\\ 5x \equiv 5\mod 6 \end{cases}$$ We can't use Chinese remainder theorem because $\gcd(8,6) = 2 > 1$ Help me.
0
votes
1answer
23 views

Enciphered Message with linear enciphering function.

My semester tests are coming up and as I was looking through past papers I came across this question. I was missing a lot during the beginning of the year and this was no doubt covered during my ...
2
votes
3answers
47 views

$(a\mod m)/(b\mod m) = (a/b)\mod m$?

b and m are relatively prime (m is prime and $b \in \mathbb Z_m^* $). In truth, I would like to be able to get to the following point (it is a simplified example): $\frac{ab \mod m}{b \mod m} = a ...
1
vote
1answer
29 views

Solutions of $a^{2} - 2b^{2} \equiv 0$ mod $p$

I came across this question in attempting to find $p$ for which $\mathbb{Z}_{p}[\sqrt{2}]$ is a field. Consider the equation: $$a^2 - 2b^2 \equiv 0 \enspace \text{mod p}$$ For which primes $p$ is ...
0
votes
1answer
37 views

Show that x = (66B − 65a) mod 143.

For each natural number $m$ we define $J_m = \{0, 1, . . . , m − 1\}$, the set of all possible residues modulo $m$. Let $x \in J_{143}$. Define $a \equiv x \pmod{11}$, $B \equiv x \pmod{13}$ Show ...
0
votes
2answers
31 views

If $a \equiv b \bmod n$, then $\gcd(a, n)= \gcd(b,n)$ [duplicate]

Again, I have been stuck in a problem of modular arithmetic. Given that $a,b, n \in \mathbb Z $ and $n>0$ and $a \equiv b \bmod n$. Show that $\gcd(a, n)= \gcd(b,n)$.
0
votes
1answer
19 views

proof of a property of modular arithmetic

I have been stuck in a problem related to modular arithmetic. I have tried it using the generalized Euler's formula for $\gcd(a,b)=as+bt$, but have not reached the proof so far. The question is: ...
1
vote
2answers
22 views

Modular arithmetic with (mod 20)

Got a question on my midterm in discrete mathematics and I can' figure out how to approach it: $19^{3701}+1 \equiv 0\ (\textrm{mod}\ 20)$ I was thinking about Fermat´s little theorem, but the 20 is ...
5
votes
2answers
849 views

Why is $20 ≡ 2 \pmod 6\;?$

Could anyone explain to me why $20 ≡ -22 \pmod 6\;?$ At school we did the following method to find $-x \mod n$ by doing: $x \mod n$ (in this case $22 \mod 6 = 4)$ $n - r$ (in this case $6-4 = ...
0
votes
2answers
20 views

Modulo congruence

I have a problem here that I have no idea how to go about solving. It states: Let $n∈Z$ with $n>1$. (a) If $n=2k$ for some odd integer $k$, prove that $k^3≡k \pmod{2n}$. (b) If $n=2k$ for ...
0
votes
0answers
36 views

Finding set of integer pairs for which two integer polynomials intersect

I am wondering if there is a theorem in number theory that addresses the following issue: Suppose we have two polynomials, f and g, with integer coefficients. Is there a general way to find elements ...
0
votes
1answer
35 views

Why is the discrete logarithm problem in $(\mathbb{Z}_n,+)$ easy?

I have trouble understanding why the discrete logarithm problem in $(\mathbb{Z}_n,+)$ should be easy: I tried it with the following example: $$a \cdot b \equiv y \pmod {p}$$ If $a=11, b=2$ and ...
7
votes
1answer
103 views

Arithmetic background of this RNG code

I am trying to figure out the mathematical background of the random number generation of an old video game. It does iterations where it updates a 33-bit state consisting of the variables z (32-bit) ...
0
votes
1answer
13 views

Linear Congruences Examples

Solve the following linear congruences: (i) $23x \equiv 16$ mod $107$ (ii) $234x \equiv 20$ mod $366$ (iii) $234x \equiv 6$ mod $366$. I am trying to solve these through the use of the ...
0
votes
0answers
40 views

Prove $2^n \not\equiv 1 \pmod{n}$ for $n>1$ [duplicate]

Prove that $2^n \not\equiv 1 \pmod{n}$ for $n>1$. I'm asking for any advice.
0
votes
0answers
24 views

Modulo-2 arithmetic division

I been recently studying modulo 2 arithmetic addition, subtraction and division. I fully understand addition and subtraction, but I'm still not clear about division. I've made the following ...