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

4
votes
1answer
203 views

Fermat's little theorem for $n=3$

for $N > 0$, I'm trying to show Fermat's little theorem, for $3$ using the orbit stabilizer theorem: $N^3 - N$ an element of $3\mathbb{Z}\ (3 \mod \mathbb{Z})$ Pf/ we can break it down into ...
1
vote
1answer
844 views

Notation for modulo: congruence relation vs operator

If a and b are congruent modulo a number c, we might write $a \equiv b \pmod c$. When writing programs, it's often useful to compute the remainder after division, and in pseudocode we might write a = ...
1
vote
1answer
757 views

Solving modular inequalities/constraint solving

A few of my current programming problems boil down to solving inequalities over modular domains and possibility could benifit from knowledge of efficient maths/algorithms rather than brute force ...
2
votes
3answers
2k views

Find modulo of multiplication of two number?

Given $m$, $a$ and $b$ are very big numbers, how do you calculate $ (a*b)\pmod m$ ? As they are very big number I can not calculate $(a*b)$ directly. So I need another method.
2
votes
1answer
2k views

Solving/simplifying large mod

Sorry for my English, it's not my first language and that's a lot more evident when we talk about math. I'm currently taking a cryptography class in university and we have to deal with very big mod ...
1
vote
1answer
134 views

Can the following modular equation be simplified?

The following equation is used to find the inverse of the remainder. Suppose we have a whole number w, which is divided by a natural number ...
0
votes
6answers
305 views

$3k-1$ can never be a power of $4$

How could we prove that $(3k-1)$ can never be any power of $4$ with $k \in \mathbb{N} $? Please note $\mathbb{N} =\{1,2,3,\cdots \}$
1
vote
1answer
594 views

Pairing off residues modulo $p$ with their inverses

I'm stumbling over this interesting proof: Show that if $p$ is a prime number, the positive integers less than $p$, except $1$ and $p-1$, can be split into $(p-3)\over2$ pairs of integers such ...
5
votes
2answers
140 views

$(1+p)^n$ is not $1 \pmod {p^r}$ when $n < p^{r-1}$

Let $p$ be an odd prime. I know that $(1+p)^{p^{r-1}}\equiv 1 \pmod {p^r}$ but how can I prove that if $n < p^{r-1}$ then $(1+p)^n$ is not $1 \pmod {p^r}$. I tried to prove using the properties of ...
4
votes
4answers
168 views

Proving $5^n \equiv 1 \pmod {2^r}$ when $n=2^{r-2}$

How can I prove that $5^n \equiv 1 (\bmod 2^r$) when $n=2^{r-2}$? Actually what I am trying to prove is that the cyclic group generated by the residue class of $5 (\bmod 2^r)$ is of order $2^{r-2}$. ...
3
votes
3answers
685 views

Showing that $(2^a - 1)\bmod (2^b - 1) = 2^{a \; \bmod \; b} - 1 $

I've been thinking on this proof for two days. I'm stuck. Show that, $$ (2^a - 1)\bmod (2^b - 1) = 2^{a \! \! \mod b} - 1 $$ where $a,b \in \mathbb{Z}^+$. I would be happy if someone can ...
2
votes
1answer
1k views

${n \choose k} \bmod m$ using Chinese remainder theorem?

I don't really see too many sites explaining how this is done. Does anyone know how this works? I'm trying to find $\binom{n}{k}\bmod m$, where $n$ and $k$ are large and $m$ is not prime. I think it ...
1
vote
1answer
425 views

Lucas Theorem for combinatorics?

Can anyone give me an example of Lucas Theorem and how it works? What about for composite modulus?
2
votes
2answers
2k views

How to compute modular square roots when modulus is non-prime

I am trying to implement James McKee's speed-up of Fermat's factoring algorithm described at http://www.ams.org/journals/mcom/1999-68-228/S0025-5718-99-01133-3/home.html. The algorithm factors ...
2
votes
1answer
236 views

Maximum number of square roots of $a \in \mathbb{Z}_n$

What is the maximum number of square roots an element of $\mathbb{Z}_n$ can have?
6
votes
3answers
227 views

Find $ n\geq1 $ such that 7 divides $n^n-3$

Find $ n\geq1 $ such that 7 divides $n^n-3$. Here is what I found: $ n\equiv 0 \mod7, n^n\equiv 0 \mod7,n^n-3\equiv -3 \mod7$ no solution. $ n\equiv 1 \mod7, n^n\equiv 1 \mod7,n^n-3\equiv -2 \mod7 ...
0
votes
1answer
3k views

Extended Euclidean Algorithm and Chinese Remainder Theorem

EEA will find the GCD(m,n) where z = a mod m z = b mod n We can use EEA to compute CRT. The complete tutorial is found here Solving Congruences: The Chinese Remainder Theorem From ...
4
votes
3answers
763 views

How to prove $\gcd(m, n) = \gcd(-m, n)?$

Beginner question here: For a quiz on Elementary Number Theory in my Discrete Math course I was asked to prove if $\gcd(m, n) = \gcd(-m, n)$. I used the Euclidean Algorithm to show that the two ...
6
votes
4answers
454 views

How can I show $e^2 \equiv 1 \bmod 24$, given that $\gcd(e, 24) = 1$?

The problem comes from a practice final for a final exam I have later today. It says "Show that if $\gcd(e, 24) = 1$ then $e^2 \equiv 1 \bmod 24$". I found that Euler's totient function $\phi(24) = ...
1
vote
0answers
99 views

How do you find small coefficients that satisfy a particular modular equation

Let's say $p=16301$. How do I best find sets of small values for $a$, $b$ and $c$ for an equation like $$a p^3+b p^2+c p=11263 \mod\ 2^{16}.$$ I can use the ...
2
votes
1answer
110 views

Solving for the smallest $x$ : $1! + 2! + \cdots+ 20! \equiv x\pmod 7$

I know the smallest $x \in \mathbb{N}$, satisfying $1! + 2! + \cdots + 20! \equiv x\pmod7$ is $5$. I would like to know methods to get to the answer.
2
votes
5answers
473 views

Quadratic congruence and primitive roots

From Apostol Chapter $10$ q$6$: Assume $m>2$, $(a,m)=1$ and there exists an $x$ such that $x^2\equiv a \pmod m$. Prove that $x^2\equiv a \pmod m$ has exactly two solutions iff $m$ has a primitive ...
4
votes
4answers
3k views

Difficulty in finding modulus of fraction

It is quite easy to evaluate $\frac{a}{b}\bmod m$ when $a$, $b$ and $m$ are integers and $\gcd(b,m)=1$ by replacing $\frac{1}{b}$ with an inverse of $b$ modulo $m$. But, is it possible to evaluate ...
1
vote
1answer
160 views

A rule to determine the crossed out digit

Lets take any integer, $z=abc\cdots$, form the sum of its digits, $a+b+c+\cdots$, subtract this from $z$, cross out any one digit from the result, and denote the sum of the remaining digits by $w$. ...
2
votes
1answer
180 views

Complexity of Gauss elimination over ring $Z_n.$

Is there some polynomial upper-bound for Gauss elimination over ring $Z_n$? I'm interested in polynomial bound depending from size of matrix and $\log n$. I also have the same question about the ...
1
vote
2answers
143 views

Compositeness of number $k\cdot 2^n+1$?

Every odd prime number can be expressed in the form $k \cdot 2^n+1$ ,where $k$ is an odd number . For $n>2$ number $k \cdot 2^n+1$ is composite if : $1.$ $k\equiv 1 \pmod {30} \land (n\equiv 2 ...
2
votes
1answer
194 views

How to go from Fermat’s little theorem to Euler’s theorem thought Ivory’s demonstration?

Ivory’s demonstration of Fermat’s theorem exploit the fact that given a prime $p$, all the numbers from $1$ to $p-1$ are relatively prime to $p$ (obvious since $p$ is prime). Ivory multiply them by x ...
-1
votes
1answer
62 views

Dr. Miller's daughter was born 421 months ago. Answer the two questions using modular arithmetic

a) in which month was she born? b) how old is she? This question has to be used by modular arithmetic...do you use mod 12 to figure out what month she was born?
0
votes
3answers
82 views

Does $a \equiv b \pmod n$ mean $n \mid a - b$ or $n \mid b -a$

If I have $a \equiv b \pmod{n}$, it means $n \mid b - a$. But can you write it as $n \mid a - b$ as well?
8
votes
1answer
1k views

Is there a way to find the first digits of a number?

Is there a way to find the first digits of a number? For example, the largest known prime is $2^{43,112,609}-1$, and I did sometime before a induction to find the first digit of a prime like that. ...
0
votes
3answers
69 views

Prove how many distinct elements in the set $\{ax \pmod{m}:a\in\{0,…,m-1\}\}$

There are $\dfrac{m}{\gcd(m,x)}$ distinct elements in the set $\{ax \pmod{m}:a\in\{0,...,m-1\}\}$ I have only known these by using a computer to generate the number of distinct elements. But I am not ...
4
votes
3answers
222 views

Find the remainder of $1234^{5678}\bmod 13$

Find the reminder of $1234^{5678}\bmod 13$ I have tried to use Euler's Theorem as well as the special case of it - Fermat's little theorem. But neither of them got me anywhere. Is there something ...
3
votes
3answers
162 views

Prove equations in modular arithmetic

Prove or disprove the following statement in modular arithmetic. If $a\equiv b \mod m$, then $ a^2\equiv b^2 \mod m$ If $a\equiv b \mod m$, then $a^2\equiv b^2 \mod m^2$ If $a^2\equiv b^2\mod m^2$, ...
3
votes
2answers
164 views

Proof that the relation $5 \mid (a + 4b)$ is symmetric and transitive

Take the relation $R$ to be defined on the set of integers: $$aRb \iff 5 \mid (a + 4b)$$ As part of a larger proof, I have to show that $R$ is both symmetric and transitive. I'm lost. I see the ...
2
votes
2answers
96 views

If $x^2 \equiv a \pmod n$, then $x^2 \equiv a \pmod {p_i}$, where $n=p_1^{t_1} \dots p_r^{t_r} $: why?

Now I'm not sure why the following holds: If $x^2 \equiv a \pmod n$ for some $x \in \mathbb Z$, then $x^2 \equiv a \pmod {p_i}$ for all $i$, where $n=p_1^{t_1} \dots p_r^{t_r}$. I know that if ...
3
votes
3answers
1k views

Finding the last two digits of $6543^{210}$

I have to find the last two digits of $6543^{210}$, my strategy is to use the Euler theorem and then some algebra to reduce this to $6543^{10}$, however I can't think of any easy way to proceed after ...
4
votes
4answers
950 views

Which is the easiest and the fastest way to find the remainder when $17^{17}$ is divided by $64$?

Which is the easiest and the fastest way to find the remainder when $17^{17}$ is divided by $64$?
2
votes
3answers
1k views

I don't understand why the inverse is this?

my question is related to matrix inverting and Hill cipher(you don't have to know what it is to help me) My teacher gave me an example. First we have a matrix (the key matrix) that multiplied by a ...
1
vote
3answers
202 views

Summing a function using modulus

The problem: If the infinite sum of a function is known, how to find: $$\begin{align*} \sum_{i\equiv 0 \mod m}f(x_0+i)=\\ f(x_0)+f(x_0+m)+f(x_0+2m)+f(x_0+3m)+\ldots \end{align*}$$ And if the ...
2
votes
2answers
88 views

Finding a solution of $x^{2}=a \pmod p$

Let $p$ be a prime which is $5 \pmod {8}$. Let $r$ be an element of $\mathbb{Z}/p\mathbb{Z}^*$ of order $4$ and let $a$ be a quadratic residue modulo $p$. Prove that a solution of $x^{2}=a \pmod p$ is ...
1
vote
2answers
485 views

Question about CRT

The question rephrased and compressed: Let $F=F_2[a]$ be a finite extension field of the field of two elements $F_2$. We are given a polynomial $R(X)\in F[X]$, and pairwise coprime irreducible ...
1
vote
1answer
97 views

How is this not an equivalence relation?

If we have a relation $\sim$ on $\mathbb{Z}/6\mathbb{Z}\times (\mathbb{Z}/6\mathbb{Z}\setminus\{0\})$ so that $(w,x)\sim(y,z)$ if $wz=xy$, how is $\sim$ not an equivalence relation?
4
votes
1answer
598 views

Why is $n\choose k$ periodic modulo $p$ with period $p^e$?

Given some integer $k$, define the sequence $a_n={n\choose k}$. Claim: $a_n$ is periodic modulo a prime $p$ with the period being the least power $p^e$ of $p$ such that $k<p^e$. In other words, ...
1
vote
1answer
200 views

Multiplicative inverse trouble in RSA Wikipedia entry

I'm having a bit of trouble working through an example in the RSA entry on Wikipedia. At step 5, $d$ is calculated as $2753$. However, $d$, which is the multiplicative inverse of $e$, can be ...
2
votes
2answers
61 views

if $ax|n$ and $ax+1$ is prime does $ax+1|a^{n}-1$?

Are there any $a,x,n$ such that $ax|n$ and $ax+1$ is prime but $a^{n}-1$ is not a multiple of $ax+1$, apart from $a=x=n=1$? I had an answer to a related question earlier: Can $x^{n}-1$ be prime if ...
10
votes
4answers
1k views

How do I compute $a^b\,\bmod c$ by hand?

How do I efficiently compute $a^b\,\bmod c$: When $b$ is huge, for instance $5^{844325}\,\bmod 21$? When $b$ is less than $c$ but it would still be a lot of work to multiply $a$ by itself $b$ times, ...
4
votes
5answers
267 views

What is modulo arithmetic

I'm trying to understand what mod means in this equation and how to solve it: d * 13 = 1 mod 1680 This is from how to make a public and private key pair. The ...
4
votes
3answers
154 views

Calculate $11^{35} \pmod{71}$

Calculate $11^{35} \pmod{71}$ I have: $= (11^5)^7 \pmod{71}$ $=23^7 \pmod{71}$ And I'm not really sure what to do from this point..
4
votes
3answers
927 views

Calculating $17^{14}\mod{71}$ using Fermat's little theorem

Calculate $17^{14} \pmod{71}$ By Fermat's little theorem: $17^{70} \equiv 1 \pmod{71}$ $17^{14} \equiv 17^{(70\cdot\frac{14}{70})}\pmod{71}$ And then I don't really know what to do from this point ...
0
votes
1answer
266 views

Multiplication and Subtraction in Modular Arithmetic

How would I determine whether $a^2-3b^2=0 \pmod 7$? By trying all values of $a$ and $b$ it is clear that this is only true for $a=b=0$, but I need a way to show this algebraically so that I can ...