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

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
756 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
158 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
179 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
946 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
484 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
595 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
153 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
908 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
264 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 ...
4
votes
5answers
291 views

What is the remainder of $(14^{2010}+1) \div 6$?

What is the remainder of $(14^{2010}+1) \div 6$? Someone showed me a way to do this by finding a pattern, i.e.: $14^1\div6$ has remainder 2 $14^2\div6$ has remainder 4 $14^3\div6$ has remainder 2 ...
0
votes
2answers
118 views

How to divide $2x \equiv 4 \pmod {7}$ to get just $x \equiv \Box \pmod{7}$

I've got three simultaneous congruence to solve, which I now know how to do, but in this particular question, one of them is in the form of $2x \equiv$ instead of of $x \equiv$ that I'm used to: ...
5
votes
5answers
3k views

Solving simultaneous congruences

Trying to figure out how to solve linear congruence by following through the sample solution to the following problem: $x \equiv 3$ (mod $7$) $x \equiv 2$ (mod $5$) $x \equiv 1$ (mod $3$) Let: ...
2
votes
5answers
208 views

Confused about modular notations

I am little confused about the notations used in two articles at wikipedia. According to the page on Fermat Primality test $ a^{p-1}\equiv 1 \pmod{m}$ means that when $a^{p-1}$ is divided by $m$, ...
2
votes
2answers
396 views

Use congruences to show that $6$ divides $n^3 – n$ for every integer $n$

Use congruences to show that $6$ divides $n^3 – n$ for every integer $n$. I did this same problem using induction, and I don't understand how to do it using congruences. Is this using modulo?
0
votes
2answers
144 views

Multiplicative order bounds

For the equation $b^k\equiv 1 \pmod p$, where $p$ is prime, how do I find a lower bound for $p$ such that $k$ will never be smaller than a given number, no matter how large $p$ gets?
1
vote
1answer
134 views

Let $y_{1},…,y_{k}$ be in $\mathbb{Z}$. Show that $\exists y \in \mathbb{Z}$ so that $y\equiv y_{1} \pmod {m_1},\dots,y \equiv y_{k} \pmod {m_k}$

Let $k\ge 2 $ and $m_{1},\ldots,m_{k}$ in $\mathbb{N}$ with $\gcd(m_{i},m_{j})= 1 \ (i \ne j)$. We show that $f(x) = x,\ldots,x)$ ist a ring isomorphism $f: \mathbb{Z}/ m\mathbb{Z} \rightarrow ...
1
vote
2answers
118 views

Sums of truth-table values mod 2 range over all truth tables

Let $A=\lbrace0,1\rbrace$. There are 16 distinct functions $f_i:A^2\to A$. Choose a permutation $P=\left(a_1,\ldots,a_4\right)$ of the elements of $A^2$, and for each $i$ consider the ordered ...
2
votes
1answer
1k views

Quick algorithm for computing orders mod n?

Is there a fast way to compute the order of $a \pmod n$ without computing potentially all the powers of $a$ up to $n-1$? For example, in computing the order of $87 \pmod {101}$, the naïve way could ...
2
votes
2answers
807 views

Schönhage-Strassen multiplication

I am trying to implement the Schönhage-Strassen algorithm (SSA) for multiplying large integers, but it only gives the right result if all $\delta_j$ are zero. I'll explain what I mean by this: SSA ...
6
votes
1answer
64 views

Is there always a primitive m-th root of unity with imaginary part bigger than 1/2

Let $m$ be a positive integer. I need the existence of a primitive $m$-th root of unity $\zeta_m$ such that its imaginary part is strictly greater than $1/2$. We can write $\zeta_m = \exp(2\pi i ...
0
votes
2answers
177 views

Why is this not working? (Chinese remainder theorem weird result)

Trying to find $x \equiv_{17} -4$, $x \equiv_{23} 3$. OK, so $x = -4 + 17k$ for some $k$. $-4 + 17k \equiv_{23} 3$. Since $19$ is the inverse of $17 \pmod {23}$, $k \equiv_{23} (3+4)19 \equiv ...
3
votes
1answer
299 views

Is this a good proof of Wilson's theorem? — ($(n-1)!+1 \equiv_n 0$ iff n is prime)

Theorem: $(n - 1)! + 1 \equiv_n 0$ if and only if $n$ is prime. To prove that if $n$ is not prime this is not true is trivial, so I'm just interested in proving that this is true for all p: ...
6
votes
4answers
1k views

calculating n choose k mod one million

I am working on a programming problem where I need to calculate 'n choose k'. I am using the relation formula $$ {n\choose k} = {n\choose k-1} \frac{n-k+1}{k} $$ so I don't have to calculate huge ...
3
votes
1answer
601 views

How many different basis' exist for an n-dimensional vector space in mod 2?

Imagine a 2-dimensional vector space in $\mathbb{Z} /2 \mathbb{Z}$. The only possible basis' are $$ \left(\begin{array}{c} 1\\ 0 \end{array}\right), \left(\begin{array}{c} 0\\ 1 ...