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
0answers
69 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
201 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 ...
1
vote
2answers
59 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
20 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
54 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
38 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
51 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
3answers
388 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
3answers
724 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
18 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
77 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
48 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
73 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 ...
0
votes
1answer
51 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
62 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
67 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
31 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
103 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
886 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
43 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
1answer
38 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 ...
8
votes
1answer
142 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
48 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 ...
1
vote
1answer
43 views

Modular exponentiation twice over

What is a general way to calculate something like $2147089412^{1147068432^{647017654}}$ mod m? It looks like modular exponentiation, but how do you reduce the highest part properly? Note: $m$ is ...
4
votes
2answers
44 views

$x^2$ $\equiv$ $1$ $\mod{p}$

Can someone provide the proof that $x^2$ $\equiv$ $1$ $\mod{p}$ iff $x\equiv1 \mod{p}$ or $x\equiv p-1 \mod{p}$, where $p$ is a prime? The argument I have in mind is setting up a bijection, like in ...
1
vote
1answer
84 views

Solve the following congruence for x (Modulo Question)

I need help in a question that I'm having a hard time understanding... It is asking to determine the congruence for $x$ and expressing the answer in the range 0-1000: $$ 200 . x = 13 \pmod{1001} $$ ...
0
votes
1answer
94 views

Is there any convention regarding the order of operation of the binary modulo operator?

Is there any predominant convention as to where the binary modulo operator (i.e., the variant of the modulo operator that is not applied to a whole equation) ranks in the order of operations, in ...
2
votes
3answers
395 views

Is modular arithmetic defined for all rational numbers (with denominators coprime to modulus)?

In the expression $\frac{1}{b}\pmod m$, where $(b,m)=1$, is $\frac{1}{b}$: a) a rational number (and so rational numbers are defined in modulo arithmetic using multiplicative inverses)? b) just ...
1
vote
1answer
43 views

Computation of large powers

How do I check if $2^{123456789}$ is divisible by 9? I tried using modular exponentiation but it is way too tedious. Is there an easier or faster way to solve it? Thanks!
3
votes
1answer
66 views

Finding a lower bound to the probability that a number will be shown to be composite?

Given the following method to decide whether a number $m$ is prime or not: Choose a random number $1<a<m-1$, and check whether $a^{m-1} = 1 \mod m$. If its equal, return true, otherwise - ...
2
votes
1answer
41 views

Primitive roots for a number

I want to show if a number a is a primitive root$\pmod{n}$ Is there a way to show this without raising a to all the powers between 1 and n-1?
1
vote
1answer
221 views

Internal and Direct Product question, need help with explanation

I am asked to express a group G={1,7,17,23,49,55,65,71} under multiplication modulo 96 as an external and internal direct product of cyclic groups. However I also have an example to help with it, but ...
2
votes
2answers
58 views

A question on divisibility

For what values of $x,y \in \{1,2,3,...9 \}$, does $$10x+y \space\mid 100x + y $$ ? What approach should I take for solving this problem ?
1
vote
2answers
171 views

Principal Square Root mod

"Theorem: let p be a prime satisfying $p=3\bmod4$. Then for an integer y which is a square modulo p, $x=y^{(p+1)/4}\bmod p$ is a square root mod p of y. That is, $x^2=y\bmod p$. This is called the ...
0
votes
0answers
126 views

Strong pseudoprime base b

Show that the composite number 1281 is a strong pseudoprime base 41. "$n-1=2^rm$, then n is a strong pseudoprime base b if either $b^m=1modn$ or $b^{2^sm}=-1modn$" Ok so I have $n=1281$ and $b=41$ ...
0
votes
3answers
37 views

Modular equations: where did I make a mistake?

I want to solve the simultaneous congruences $$\begin{cases} 2x \equiv 4 \mod 8 \\ x \equiv 2 \mod 6 \end{cases} $$ My solution: $$2x \equiv 4 \mod 8 \iff x = 4l + 2 $$ $$x \equiv 2 \mod 6 \iff 4l + ...
0
votes
4answers
47 views

Modular arithmetic, very simple implications.

$$3t \equiv 1 \mod 4 \Rightarrow t \equiv 3 \mod 4 $$ I don't understand that, so I'm asking for explain me. Thank, in advance, greetings.
0
votes
4answers
351 views

Finding divisibility of a number using modular arithmetic

Let N = 12345678910111213141516171819. How can I use modular arithmetic to show that N is (or isn't) divisible by 11? In general, how can I apply modular arithmetic to determine the divisibility of an ...
0
votes
2answers
33 views

Question about modular arithmetic notation

In this document: http://cims.nyu.edu/~kiryl/teaching/aa/les092603.pdf The ordered pair notation is used but it is never explained what it means. ex: ...
0
votes
1answer
56 views

Proof, that $a \equiv 1 \pmod{p}$

Let $n \in \mathbb{N}^{+} \smallsetminus \{{1}\}$ and $p = min\{p \in \mathbb{P} : p \mid n\}$. Also, let $a \in \mathbb{Z}$ and $a^n \equiv 1 \pmod{n}$ I need to proof, that $a \equiv 1 \pmod{p}$. ...
2
votes
1answer
95 views

How to show a number is not a sum of three squares

I've been tasked with the following: Let $m$ and $n$ be positive integers, prove that $4^{n}(8m+7)$ cannot be written as the sum of three squares. I've already gotten the idea that I should do ...
1
vote
1answer
44 views

Modular arithmetic and using in well-ordering principle

I need to prove the following, but I do not know how to go about it. If $$ (*)\:\:\: x^{3} - y^{3}= 3^{n} $$ Then $$ x \equiv 0 (mod 3) \:\: and \:\:\: y \equiv 0 (mod 3)$$ In addition, ...
-1
votes
2answers
121 views

Units in the ring $\mathbb{Z}(\omega)$

If $\omega \not= 1$ is a cube root of unity in $\mathbb{C}$, show that the units in the ring $\mathbb{Z}[\omega]$ are the elements of modulus 1. Hence, or otherwise, show that $U(\mathbb{Z}[\omega]$ ...
2
votes
1answer
100 views

computing $29^{25}$ (mod 11)

I'm trying to learn how to use Fermat's Little Theorem. $29=2\cdot11+7 \Rightarrow 11\nmid29$ by the theorem we have $29^{10}\equiv 1$(mod 11) $25=10\cdot 2 + 5$ $ ...
0
votes
1answer
408 views

Calculating nCr mod M using inverse multiplicative factors

The method used for calculating nCr mod M is: fact[n] = n * fact[n-1] % M ifact[n] = modular_inverse(n) * ifact[n-1] % M And then nCr is calculated as ...
2
votes
0answers
53 views

Compute digits of a number.

The question is what the last $10$ decimal digits of $2^{3^{4^{5^{6^{7^{8^9}}}}}}$ are? I do not get the following solution and its motivation. I would appreciate if someone would shed light on it. ...
4
votes
1answer
142 views

Congruence for the sums of odd powers of integers [duplicate]

Does someone know how to prove ***EDIT by induction**** that for all integers $n\ge1$, $k\gt0$ $$\sum\limits_{i=1}^{n} {i^{2k+1}}\equiv 0\ \ \ \pmod{\frac{n(n+1)}{2}}$$ I thought this should be a ...
7
votes
1answer
108 views

Infinitely many primes can not be written as the sum of three squares

Prove that there are infinitely many prime numbers $p$ such that $x_1^2+x_2^2+x_3^2 = p$ has no solutions. So my attempt is the following. Let's look at residues modulo $8$. $x^2$ is either $4$ or ...
0
votes
2answers
35 views

Prove divisibility

We have the following proposition: $$P(n): 13^n+7^n-2\vdots 6$$. Prove $P(n)$ in two ways. I know that one of them is mathematical induction. I don't know many things about the other one, I know ...
0
votes
2answers
20 views

Inverse of $3$ in $\mathbb{Z}_7$ using Fermat's Theorem or its corollaries.

What is $3^{-1}$ , the multiplicative inverse of $3$ in $\mathbb{Z}_7$. Use Fermat's Theorem or its collaries. How do I make use of the Fermat's theorem to solve this? I know how to solve it using ...