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

2
votes
1answer
123 views

Is the modular multiplicative inverse of $a$ equal to that of $-a$?

In javascript, I am implementing Lagrange interpolation over a finite field $GF_p$ for some prime $p$. I only need to compute the value of the $y$-intercept of the Lagrange interpolation polynomial ...
0
votes
3answers
151 views

What is the solution for $(x^2- 1) \bmod 8= 0$

I could not figure out the solution of $(x^2- 1) \bmod 8= 0$ Thank you.
2
votes
2answers
95 views

How do you solve the following a - b(mod5) = a + b(mod5)?

attempted solution: a - b(mod5) = a + b(mod5) 2a(mod5) = 0 a = 5 5 + b mod 5 = 5 - b mod 5 b mod 5 = -b mod 5 b = 0
0
votes
2answers
92 views

How do evaluate $x = (5^2 \bmod 6)^4 \bmod 15?$

$x = (5^2 \bmod 6)^4 \bmod 15$. I wanted to turn $(5^2 \bmod 6)^4 \bmod 15$ into a constant, but I just lost hope when I saw how humongous the expression was.
1
vote
3answers
99 views

Solve $x\equiv 2\pmod 5, x\equiv 1\pmod 8, x\equiv 7\pmod 9, x\equiv -3\pmod {11}$ for $x\in\mathbb Z$.

Solve $x\equiv 2\pmod 5, x\equiv 1\pmod 8, x\equiv 7\pmod 9, x\equiv -3\pmod {11}$ for $x\in\mathbb Z$. $x\equiv a_i\pmod {m_i}$ The system of congruences has a unique solution modulo M($m_1, m_2, ...
2
votes
2answers
110 views

Why is $x^7 = x$ true for every $x$ in $x ∈ Z/14Z$?

I'm trying to solve $x^7 = x$ in $x ∈ Z/14Z$. I tried it in Wolfram Alpha and I know it's true for every $x$ but I don't know why. Any help appreciated.
2
votes
2answers
80 views

Modular Arithmetic Equations

I'm trying to solve $x^{16} = [1]_{989}$ in $x ∈\Bbb Z/989\Bbb Z$. I tried a few simplifications but don't know how to solve it. Any help is welcome.
0
votes
2answers
237 views

Compute $\phi(24)$. For each element $\mathbb Z /24$ decide whether the element is a unit or a zero divisor. [duplicate]

Possible Duplicate: Euler $\Phi$ Function $$\underline{Question}$$ Compute $\phi(24)$. For each element $\mathbb Z /24$ decide whether the element is a unit or a zero divisor. If the ...
3
votes
3answers
281 views

What are $2222^{5555}+5555^{2222} \pmod 7$ and $9^{2n+1}+8^{n+2} \pmod{73}$?

Tell me hint for solve : 1) $ 2222^{5555}+5555^{2222} \equiv \mathord? \pmod 7$ 2) $ 9^{2n+1}+8^{n+2} \equiv \mathord ?\pmod{73}$ thank you.
1
vote
0answers
109 views

Cycle of remainders

Let $N, K, W$ be natural numbers If I start from $R_0$, say any integer $r_0, 0 \lt r_0 \lt N$ and proceed with: $$R_j = ( R_{j-1} + K ) \mod W,\quad j=1,2, \dots$$ (that is the remainder of the ...
0
votes
2answers
526 views

Solving systems of basic congruences

I'm having some difficulty with a problem and I was hoping I could find some help here. We've been covering congruences in my Discrete Math class, and, while I understand what they mean, I can't seem ...
3
votes
1answer
451 views

Could anyone explain how my textbook gets this modulu congruence statement?

We say that two integers a and b are congruent modulo m if a − b is divisible by m. We denote this by a≡b (mod m). Example 1: −31 ≡ 11 (mod 7) 11 mod 7 is 4, is it not? -31 ≠ 4 last time I checked.
1
vote
1answer
108 views

How can I find this result modulo $10^8$?

Let $\;\;\displaystyle x=\left \lfloor\frac{\sqrt{4N+(2a+1)^2}-1}{4}\right\rfloor\bmod10^8 \;\;\text{ where}\; N,a \text{ are integers.}$ When $N$ and $a$ are sufficiently large, this expression ...
3
votes
5answers
90 views

Proof using Mod

How can you prove that: $$a^7\equiv a\:(\text{mod } 42)$$ I haven't been given any other information other than to use Fermat's theorem.
1
vote
1answer
109 views

Euler Fermat Theorem with composites

Show that for every integer $a$ such that $\gcd(a,100)=1$, $a^{100}= 1 \mod 100$ and use this to compute the last two digits of $(11)^{102}$. Can you say something more precise about the order of ...
1
vote
0answers
86 views

Need help simplifying an equation.

I'm trying to speed up the following code: sum = 0 for (k = 1 ... N) { f = Fibonacci(k); for (a = 1 ... 24) for (b = 1 ... 24) for (c = 1 ... 24) { sum = sum + m(a, b, c) // ...
2
votes
2answers
75 views

Generic Question Regarding modular arithmetic

I was going over a paper regarding linear algebra and its relation to chaos. One particular section focuses on Arnold's cat map. It briefly mention modular arithmetic. In this case, it dealt with ...
1
vote
1answer
84 views

Theorem about mod n, when n is square free

Let $n\in \mathbb{N}$. Show that if $n$ is square-free, then there exists an integer $u > 1$ such that $a^{u} ≡_{n} a $ for all $a \in \mathbb{Z}$. This is my attempt to prove it. For $n = ...
1
vote
3answers
197 views

Not understanding modulo

I'm not sure if I'm in the right place, but I'll give it a try! I'm very bad with mathematics even though it's pretty interesting. Well, for Java programming we have to use the modulo operator, but I ...
3
votes
2answers
178 views

$p$ an odd prime, $p \equiv 3 \pmod 8$. Show that $2^{(\frac{p-1}{2})}*(p-1)! \equiv 1 \pmod p$

$p$ an odd prime, $p \equiv 3 \pmod 8$. Show that $2^{\left(\frac{p-1}{2}\right)}\cdot(p-1)! \equiv 1 \pmod p$ From Wilson's thm: $(p-1)!= -1 \pmod p$. hence, need to show that ...
1
vote
2answers
214 views

Solving an equation in modular arithmetic

Given $A, B, C$ positive integers, $B < C,$ I would like some thoughts about (possibly efficient) ways to find the smallest integer $X$, where $0 < X < C$, such that: $$A X + B \pmod{C - ...
0
votes
2answers
77 views

Computing $\left\lfloor\sum_{k = 1}^{n}{\varphi^{3k}}\right\rfloor$

I'm trying to find $\left\lfloor\sum_{k = 1}^{n}{\varphi^{3k}}\right\rfloor$ mod $m$. $\varphi = \frac{1 + \sqrt{5}}{2}$ and $\varphi^3 = 2 + \sqrt{5}$. But honestly I'm not even sure where to start. ...
3
votes
4answers
618 views

How do I subtract times?

I have an embarrassingly basic modular arithmetic question. I understand that I can subtract, for example, 1 hour from 10 o'clock to get 9 o'clock, or even 2 hours from 1 o'clock to get 11 o'clock; ...
0
votes
1answer
1k views

how many 2x2 matrices are invertible in mod p

I am trying to solve this problem for homework but unable to get anything. The question is to find the number of invertible 2x2 matrices in mod p? Each entery can bee from the set ...
0
votes
3answers
69 views

elementary congruence statement proof

it is me again :), i am trying to prove this statement of congruence, the statement is as follows: $a \equiv b \mod m \Longrightarrow a^{k} \equiv b^{k} \mod m $ for all $ k \in \mathbb{N}$ i ...
1
vote
2answers
69 views

congruence theorem prove

i am trying to prove this statement of congruence which is not really hard, but i am stumbling across the simple step. statement: $a \equiv b \mod m \land c \equiv d \mod m \Longrightarrow ac ...
3
votes
1answer
94 views

Is there a way to find the value of $1^n+ 2^n +\cdots + m^n$ modulo $x$?

I am writing a program in which I want to make changes to make it more efficient. What the program does is it takes three inputs $m$, $n$ and $x$ and I have to find the value of the following ...
0
votes
2answers
241 views

Showing $1+p$ is an element of order $p^{n-1}$ in $(\mathbb{Z}/p^n\mathbb{Z})^\times$

I'm trying to work through Dummit & Foote, but I've gotten stuck on the following question: Let $p$ be an odd prime and let $n$ be a positive integer. Use the binomial theorem to show that ...
2
votes
1answer
85 views

$x^y \bmod n$ seems to repeat itself after some steps (when iterating over $n$)

Given $1516^{2627} \bmod 13$ I tried several things to find the solution without a calculator, such as examining some powers like $1516^{1} \bmod 13$, $1516^{2} \text{mod} 13$, $1516^{3} \bmod 13$ and ...
0
votes
3answers
124 views

How to compute large modulos with pen and paper?

I would like to compute $47^{9876543210} \bmod 9$ and $48^{12345678901234567890} \bmod 9$ with pen and paper. I know this is similar to computing $2^{9876543210} \bmod 9$ and ...
1
vote
2answers
147 views

Fastest way to compute [1234567890]_200 with pen and paper

I'm wondering if there is a more elegant and faster way to compute $1234567890 \bmod 200$ with pen and paper than doing the arithmetic division. Thanks
1
vote
1answer
33 views

Proof help needed about order of a number & congruences

$\def\ord{\operatorname{ord}}$I could not prove the following statement. Could you please help me? Let $\ord_p a = p-1$. Show that for every $c∈\mathbb Z$, $\gcd(c,p)=1$, there exists $1≤i≤p-1$ such ...
1
vote
1answer
181 views

linear equations - under modulo

I'm having difficulties proceeding with this problem: We have the following linear equations: $$\begin{array} 1x + 2y + 2z = 0 \\ 3x – 2y + 2z =1\\ 2x + y + z =3\end{array}$$ ...
1
vote
2answers
126 views

Modular Arithmetic and the Order of the Monster

I am trying to verify directly using modular arithmetic that $|M|/(40*41) \equiv 1$ mod $41$, where $M$ is the monster group. I am not really sure how to approach this type of problem, i.e. one ...
0
votes
2answers
285 views

calculate with large exponents

Can somone explain me, how I can check if an number is an divisor of a sum with large exponents? Something like this: Is $5$ a divisor of $3^{2012} - 4^{2011}$? And how can I calculate ...
1
vote
0answers
135 views

How to proof this equation without calculating the values it self

I have the following equation. $$(X + a)^n\equiv(X^n + a)(X^r - 1)\bmod n.$$ This is part of the AKS algorithm. The problem is, that I'll have to solve this equation for every $1\leq a<10$ and ...
0
votes
1answer
125 views

Prove that there are $p+1$ points on the elliptic curve $y^2 = x^3 + 1$ over $\mathbb{F}_p$, where $p > 3$ is a prime such that $p \equiv 2 \pmod 3$.

Let $p > 3$ be a prime such that $p \equiv 2 \pmod 3$. Define the elliptic curve $E$ over $\mathbb{F}_p$ by $y^2 = x^3 + 1$. Prove that $E(\mathbb{F}_p)$ consists of $p+1$ points. Using Fermat's ...
1
vote
2answers
208 views

Proof using Fermat's Little Theorem

Use Fermat's Little Theorem to prove that $11|(9n^{23}-5n^{13}+7n^3)$
11
votes
2answers
221 views

Is my shorter expression for $ s_m(n)= 1^m+2^m+3^m+\cdots+(n-1)^m \pmod n$ true?

I'm considering the following sums for natural numbers n,m $$ s_m(n)= \sum_{k=1}^{n-1} k^m =1^m+2^m+3^m+\cdots+(n-1)^m $$ modulo n . Looking at odd n first, I found by analysis of the pattern of ...
1
vote
2answers
70 views

Find the inverse of $\alpha^{38}$ in $\mathbb F = \mathbb Z_2[x]/\left<x^4+x+1\right>$

Let $\alpha$ be a root of $x^4+x+1$ and we are given some powers of $\alpha$ as linear combinations of $1,\alpha,\alpha^2$ and $\alpha^3$ $\alpha^4=\alpha+1$ $\alpha^5=\alpha^2+\alpha$ ... (the rest ...
5
votes
3answers
537 views

How to calculate $3^{45357} \mod 5$?

I wrote some code, here is what it gives: \begin{align*} 3^0 \mod 5 = 1 \\ 3^1 \mod 5 = 3 \\ 3^2 \mod 5 = 4 \\ 3^3 \mod 5 = 2 \\\\ 3^4 \mod 5 = 1 \\ 3^5 \mod 5 = 3 \\ 3^6 \mod 5 = 4 \\ 3^7 \mod 5 = 2 ...
4
votes
2answers
93 views

Deciding if a univariate quartic has a solution mod p

I have an equation in $x$ and I would like to determine if it has any solutions modulo a large prime $p$. Suppose $p$ is large enough that I can factor numbers up to $p$, but I cannot test all values ...
0
votes
3answers
212 views

How to find the inverse of integer $i$ in $\mathbb Z_{n}$

In my understanding, a number $i$ has an inverse $i^{-1}$ in $\mathbb Z_{n}$ if $i\times i^{-1} \equiv 1 \pmod{n}$ e.g.: In $\mathbb Z_{14}$ the inverse of $3$ is $5$ since $3\times5\equiv1\pmod{14}$ ...
2
votes
3answers
48 views

Prove $3^{2n+1} + 2^{n+2}$ is divisible by $7$ for all $n\ge0$

Expanding the equation out gives $(3^{2n}\times3)+(2^n\times2^2) \equiv 0\pmod{7}$ Is this correct? I'm a little hazy on my index laws. Not sure if this is what I need to do? Am I on the right ...
0
votes
3answers
38 views

Why is an element $g$ not primitive$\pmod{n}$ if $g^\frac{n-1}{f} \equiv 1\pmod{n}$ for some prime factor $f$ of $n-1$?

So a primitive root/element $g$$\pmod{n}$ is an element in $\mathbb Z^*_{n}$ such that when $g$ is raised to each element in $\mathbb Z^*_{n}$ it generates the whole set of $\mathbb Z^*_{n}$ But the ...
0
votes
3answers
56 views

Prove that for every integer $n$ that is not a multiple of $3$ we have $3 | (4n^{12}+3n^6+2)$

Prove that for every integer $n$ that is not a multiple of $3$ we have $3 | (4n^{12}+3n^6+2)$ So I know this has something to do with fermat/euler's theorem which says: For some $a^x \equiv y ...
1
vote
4answers
124 views

Solve $3619t = 133$ in $\mathbb Z_{4557}$

What I understand: This question asks to solve for $t$ such that when $(3619 \times t)$ is divided by $4557$ the remainder is $133$ I have found a Bezout identity $7 = 34 \times 3619 - 27 \times ...
0
votes
3answers
40 views

What are all the elements of $\mathbb Z_{2}[x] / <x^3+x+1>$

List all the elements of $\frac{\mathbb Z_{2}[x]}{<x^3+x+1>}$ (the set of remainders) Please verify my understanding: Since the polynomial is of degree 3, the remainders must have degree at ...
0
votes
1answer
55 views

How to get the equivalence classes for $m(x) = x^2+1$ in $\mathbb Z_{2}[x]$?

For $m(x) = x^2+1$ in $\mathbb Z_{2}[x]$, we have $$\frac{\mathbb Z_{2}[x]}{ \langle x^2+1 \rangle} = \{0, 1, x, x+1\}$$ How do we get that set? I think it's supposed to be a set containing all ...
2
votes
1answer
289 views

CRT representation of integers, and multiplication in (almost) linear time

From the section Open Problems in the article Connect the Stars by Kenneth Regan: Finally, we offer an intriguing open problem about how fast we can multiply integers. It is possible to multiply ...