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

-3
votes
1answer
92 views

A number Theory question : Proof of a mod

Let $a,\ b$ be integers with $b < 0$. Show that $a\pmod b \in (b,0]$
1
vote
4answers
191 views

Modular Arithmetic order of operations

In an assignment, I am given $E_K(M) = M + K \pmod {26}$. This formula is to be applied twice in a formal proof, so that we have $E_a(E_b(M)) =\ ...$. What I'm wondering is; is the original given ...
2
votes
4answers
91 views

$(2k+1)^{4k+1} = (2k+1) \pmod {4k+2} $ . . . why?

Well, this must be simple but I seem to be dense at the moment. I checked heuristically for small $k$ $$(2k+1)^{4k+1} = (2k+1) \pmod {4k+2} \tag1 $$ but couldn't prove that this is so in general. ...
1
vote
1answer
195 views

Fast modulo operation [duplicate]

Possible Duplicate: calculating $a^b \!\mod c$ I have a number of form: $p^n + p$, where $p$ is a prime number and $n$ can be any large number, for example, say $10^{12}$. What is the ...
1
vote
2answers
173 views

Modular Arithmetic on Circle

On the unit circle, what does the set $\left \{ n \bmod{2\pi}:n \in \mathbb{N}\right \}$ represent? What is the subsequentieal limits of $\left \{ \sin(n) \right \}_{n\in \mathbb{N}}$? I am probably ...
5
votes
0answers
65 views

Statement about Woodal primes.

A Woodal number is an integer of the form $n 2^{n}-1$. A Woodal prime is an integer that is both a prime and a Woodal number. Let $p$ be a prime of the form 1 mod 4. Then $p 2^{p} -1$ is never a ( ...
0
votes
3answers
483 views

Properties of Euler's $\phi()$ function

This is part of the $\phi(mn) = \phi(m)\cdot \phi(n)$ theorem. For some integer $a$ relatively prime to $m\cdot n$ how do I know the following: $a\mod m$ is relatively prime to $m$ $a \mod n$ is ...
1
vote
1answer
250 views

Prove that $a^{p-1} \equiv 1$ $\ $(mod $p$) [duplicate]

Consider the equivalence relation $m\sim n$ defined to be $\frac {m-n}p=z$ (i.e., when $m-n$ is divisible by p) where $m,n,p,z\in \mathbb{Z}$ and $p$ is prime. Now suppose that $a$ is some integer ...
2
votes
3answers
4k views

How to solve system of equations with mod?

I'm trying to solve for $a$ and $b$: $$5 \equiv (4a + b)\bmod{26}\quad\text{and}\quad22\equiv (7a + b)\bmod{26}.$$ I tried looking it up online, and the thing that seemed most similar was the Chinese ...
1
vote
2answers
216 views

When are quotient maps induced by equivalence relations surjective and injective?

Let $\sim$ be an equivalence relation on a set $X$. Also, there is a natural function $p:X\to \tilde X$ where $\tilde X$ is a set of all equivalence classes. (Equivalence classes are defined as, ...
3
votes
1answer
134 views

Summation mod$ (2^{16} +1)$

How can we calculate $\displaystyle\sum\limits_{k=1}^{2^{16}} \binom{2k}{k}(3\times 2^{14} +1)^k (k-1)^{2^{16}-1}$ mod $(2^{16} +1)$? I am aware that $2^{16} +1$ is a prime.
1
vote
1answer
64 views

Calculate $2^{1401} \pmod{2803}$

Without using the fact that 2803 is prime, Calculate $2^{1401} \pmod{2803}$ Usually I would do something like: $1401 = 3\times467$ $\equiv(2^{467})^3 \pmod{2803}$ And try to simplify it down and ...
3
votes
2answers
126 views

last digit of $n^5$ and $n$ is the same digit [duplicate]

Possible Duplicate: The last digit of $n^5-n$ Why is the last digit of $n^5$ equal to the last digit of $n$? Basically, this is the same question as Why is the last digit of $n^5$ equal ...
1
vote
4answers
693 views

Chinese Remainder Theorem and linear congruences

I have found the following congruences: $x \equiv 2\mod 5$ $x \equiv 12\mod27$ $x \equiv 2\mod4$ How can I solve for x using the Chinese Remainder Theorem? Please include justifications for the ...
1
vote
2answers
291 views

Fast Euler's Phi function and linear congruence

I am trying to solve $5k \equiv 2\mod7$ with Euler's phi function. $5$ and $7$ are relatively prime so we can write: $5^{\phi(7)} \equiv 1\mod7$. Multiply by $5^{-1}$: $5^{\phi(7)-1} \equiv ...
0
votes
1answer
48 views

Transfering algorithm into equation(s) and solving it?

Could someone for me try to transform algorithm that is in next pdf into equation(s): http://arxiv.org/pdf/math/0507011? For instance take example from page 6 for divisibility of number 16762 and try ...
1
vote
2answers
213 views

solving and manipulating linear congruences

I need to find a multiple of $5$ call it $5k$ with the following properties: $5k \equiv 3 $ mod $6$ $5k \equiv 2 $ mod $7$ My first instinct is to start with the Chinese Remainder Theorem, but I ...
1
vote
3answers
281 views

Modulus simplification

Trying to get the modulus of the five numbers immediately before a prime, added together in there factorial form; I'll call this operation $S(p)$. For example, $$S(p) = ((p-1)! + (p-2)! + (p-3)! + ...
3
votes
4answers
74 views

$Y^3$ congruent to $1 \pmod {p}$

How to get the condition on $p$ for which $y^3$ congruent to $1$ modulo $p$ has $3$ solutions ( $1$ solution $x= 1$ is always possible, right ?).
2
votes
0answers
105 views

Multiplication structure for finite abelian rings of order $p^2$.

Consider an odd prime $p$ and a positive integer $a$ as close to 2 as possible that is not a quadratic residue $mod$ $p$. If we extend the ring $mod$ $p$ with the element $b = a^{\frac{1}{2}}$ then ...
0
votes
2answers
135 views

Use Lucas' test with $a=7$ and prove $71$ is prime

My working so far: $71-1=70$ and Prime factors of $70$ are $2 \times 5 \times 7$ Check $a=7$: $7^{(\frac{70}{2})} \equiv 7^{35} \equiv x (mod 71)$ How do I find $x$? Usually I would use Fermat's ...
2
votes
1answer
78 views

Exponential modular equation

I am having some trouble in proving that the only solutions to $$ -2^{m-1} \equiv m \pmod{7} $$ are $m \equiv 3,5, 13 \pmod{42}$. What I tried to use: If $-2^{m-1} \equiv m \pmod{7}$, then ...
2
votes
1answer
506 views

Modular Arithmetic over a Matrix

What are the rules for modular arithmetic when multiplying two matrices? I want to calulate $C = AB \mod{n}.$ Aside from the obvious way of performing the modulo after the multiplication, when and ...
4
votes
1answer
191 views

gcd and fermat's little theorem

I know the following: gcd($b$, $561$) = $1$ How can I show that $b^{560}$ $\equiv$ $1$ mod $3$ ? I see that $561$ is not prime as $561$ = $3*11*17$. My first thoughts are: gcd($b$, $3$) = $1$ so I ...
4
votes
2answers
130 views

Value of $\sum_{i=1}^{p} i^k \pmod{p}$

I found a statement that $$\sum \limits_{i=1}^{p} i^k \equiv \begin{cases} -1 && (p-1) \mid k \\ 0 && \text{otherwise}\end{cases} \pmod{p}$$ for a prime $p$ and positive integer $k$. ...
2
votes
1answer
58 views

Given two integers for which I know the modulo given a divisor, what can I know of the modulo of their multiplication?

With all symbols representing integers, I know: $$ a \equiv m_a \bmod d_a \\ b \equiv m_b \bmod d_b $$ And I am now looking for $m_c$ and $d_c$ such that: $$ c = ab \\ c \equiv m_c \bmod d_c \\ ...
0
votes
2answers
109 views

Operations on Congruences

What operations can I perform on congruences to transform the modulo n? Specifically, in a formula such as Fermat's Little Theorem (or a generalization) $b^{p-1}$ $\equiv$ $1$ mod $p$ What ...
1
vote
2answers
180 views

Solving Linear Congruence

Ok, I found a lot of questions asking about solving $a = b \pmod c$ where you could divide $a$ and $b$ by some $x$ where gcd$(x, c) = 1$. How do you solve when this is not the case? Suppose I have ...
0
votes
1answer
190 views

Simple modulus algebra - rabin karp weird implementation

I'm studying the Rabin Karp algorithm and something isn't clear about the modulus algebra: Let's suppose I have all base-10 numbers for simplicity's sake $14159 = (31415 - 3 \cdot 10^4) \cdot 10 + ...
1
vote
2answers
727 views

The right way to write modulus equation?

I came from computer forum, and I came across many different expression of modulus equation, which of the following is authentic ? ...
3
votes
3answers
191 views

Proving a congruence solution is unique $\pmod {m/\gcd(c,m)}$

Prove that one can solve the congruence $cx \equiv b \pmod m \Longleftrightarrow \gcd(c,m)|b$. Show, moreover, that the answer is unique $\bmod{m/\gcd(c,m)}$ My Work Proof of $(\Rightarrow)$: ...
4
votes
2answers
113 views

Proofs using linear congruences

We have just covered solving linear congruences, and I am confused about how to use them in proofs. I understand that the linear congruence $$cx \equiv b \pmod m$$ has a unique solution $\bmod m$ if ...
6
votes
5answers
5k views

How do you calculate the modulo of a high-raised number?

I need some help with this problem: $$439^{233} \mod 713$$ I can't calculate $439^{223}$ since it's a very big number, there must be a way to do this. Thanks.
3
votes
2answers
248 views

congruence proof

I am looking into congruences for school and I have trouble understanding on how to prove this (i understand modules, congruences but don't know how to prove it). I need to prove that if this ...
2
votes
1answer
74 views

Modulo equation : $\frac{n^{k+1}-1}{n-1} \equiv a{\pmod p}$

Can we have directly answer for this question : $$\frac{n^{k+1}-1}{n-1} \equiv a{\pmod p}$$ (p is a prime and k,n is a fixed number) My question is : with fixed number n, k and p, can we know value ...
3
votes
1answer
245 views

Solvability of $x^q=2\mod p$

I've been discussing a problem recently Let $p, q$ be primes. If $x^q\equiv2\pmod p$ has no solution then $p\equiv1\pmod q.$ This is not a bi-equivalence (though it is "nearly" one): there are 811 ...
2
votes
4answers
181 views

How many solutions does equation $6x=14 \bmod 35$ in $\mathbb{Z}/35\mathbb{Z}$ have?

Yes, this is a homework problem. And no, I'm not asking for the answer to this. I just want to understand how to tackle this type of problem. What are the steps towards finding the solutions? My ...
0
votes
5answers
2k views

How is 3 modulo 5 = 3

Just tried googling but couldn't find any example, but how 3 % 5 = 3 Googled it
0
votes
1answer
51 views

How can I create a function that simulates a “linked list”?

If I have: { 0, 1, 2, 3, 4, 5, 6 } How can I make a function that will return the number of steps to a target element, in one direction? To clarify, let the target be 2... Say that x = 5, and I ...
1
vote
0answers
244 views

Modular multiplicative inverse and coprime numbers needed.

I have a 64 bit algorithm that uses modular multiplicative inverse and coprime numbers, and I need to convert it to 32 bit. This math is not my area, and I cannot find an online calculator, so I hope ...
2
votes
1answer
112 views

Problem with Modulus and division

Suppose I want to compute $(a_1 + a_2 + ... + a_n) \mod m $. For very large values of $a_i$, I can take modulo after every operation: $ [(a_1 \mod m) + (a_2 \mod m) + ... + a_n \mod m] \mod m$ (I ...
1
vote
3answers
3k views

Find the multiplicative inverse of 23 in Z26

I have no number theory training, but I did many google reading prior coming here. There are so many ways to solve this problem but I am lost. How would you find the answer to the question Find the ...
1
vote
2answers
192 views

Function with a Modular Inverse

For a combinatorics problem I have a function, $h(x)$ that is always divisible by five, but it is calculated in pieces, e.g. $h(1) = 43 + 7$. The final function that I need is $f(x) = (h(x) / 5) ...
1
vote
1answer
285 views

How to remove the denominator?

I have the following expression for $n>3$: $$\frac{5\cdot(n-1)\cdot[8\cdot\operatorname{Luc}(n) + 5\cdot\operatorname{Luc}(n-1)] + [4\cdot\operatorname{Luc}(n-1) - ...
1
vote
1answer
96 views

Solving $a + b x = c y$ in the integer domain for general $a$

I have the following equation: $\frac{a + b x}{c} \in \mathbb{N}$ where $a,b,c,x \in \mathbb{N}$. and I want to find all x that satisfy these requirements. This should be the same as: $a + b x = c ...
2
votes
2answers
117 views

What is the fastest or usual way to calculate $(\frac{x-1}{2})^2$ mod $x$ if $x$ is odd?

Because: A) for odd $x$ and $x \equiv 1\pmod {4}$ the upper formula is the same as $x - (x-1)/4$ B) for odd $x$ and $x \equiv 3\pmod {4}$ the upper formula is the same as $(x + 1)/4$ Example A) ...
0
votes
1answer
134 views

Mix of Modulus and Division

While solving problems in SPOJ, I faced cases where I need to take Modulus of Big numbers like Fibonacci with 10^9 + 7 ( say MOD ). Now, consider the following case : (Fib(n) + Fib(6*n-1)) / ...
2
votes
4answers
163 views

How to implement modular division?

I want to calculate do calculate $\frac{a}{b} \pmod{P}$ where $a$ is an integer less $P$ and $P$ is a large prime, $b=5$, a fixed integer. How can I implement it? Any algorithm which will work well?
4
votes
2answers
124 views

What's the answer of (10+13) ≡?

As to Modulus operation I only have seen this form: (x + y) mod z ≡ K So I can't understand the question, by the way the answers are : ...
1
vote
1answer
496 views

Modulo of (Power of 2 divided by a number)

I wanted to calculate the power of $2$ raised to a number $a$, divided by another number $b$ and then take the modulo $K$ of this quantity. Meaning, I basically wanted $(2^a/b) \mod K$. Take an ...