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

5
votes
2answers
36 views

Trick with modular exponentiation

For example, $$123^{25} \pmod{10}$$ $$ 123 \equiv 3 \pmod{10}$$ $$123^{2} \equiv 9 \pmod{10}$$ $$123^{3} \equiv 7 \pmod{10}$$ $$123^{4} \equiv 1 \pmod{10}$$ $$123^{5} \equiv 3 \pmod{10}$$ It is ...
5
votes
5answers
151 views

Calculate $121^{199} \mod 300$

Using Fermat's little theorem I proved that $$121^{199} = 121^{39} \mod 300$$ (as $\phi(300)$ is $80$) but I don't think I can leave it like this. My question being how can I solve ...
1
vote
2answers
42 views

Last digits using Euler's theorem

Euler's theorem says: $$a^{\varphi(m)} \equiv 1 \pmod{m}$$ Find $$22^{41} \pmod{10}$$ Obviously, you have to gun for $\varphi(10)$. Let $a = 22$ $$22^{\varphi{10}} \equiv 1 \pmod{10}$$ But ...
0
votes
1answer
19 views

How many values of $\alpha$ are in interval $[0,2\pi)$ such that $\alpha=\left(12\left(12\alpha\bmod 2\pi\right)\bmod 2\pi\right)$?

How many values of $\alpha$ are in interval $[0,2\pi)$ such that $$\alpha=\left(12\left(12\alpha\bmod 2\pi\right)\bmod 2\pi\right)$$ I first tried to split problem into cases: There are $12$ ...
1
vote
1answer
30 views

Using CRT to prove a single congruence relation

I am trying to prove that $2^{700} \equiv 1 \mod 3625$ and I am supposed to use the Chinese Remainder Theorem as part of my proof. I know that the Chinese Remainder Theorem tells me that a solution ...
0
votes
3answers
51 views

Solving a congruence in mod 59

Given that 10 is a primitive root in mod 59, I want to solve $x^{29} \equiv -1 (mod 59)$. My approach is, since 10 is a primitive root, we can set $x \equiv 10^{\bar{x}}, \Rightarrow x^{29} \equiv ...
1
vote
2answers
36 views

Solve the linear system $x \equiv 12 \pmod{25}$ and $x \equiv 2 \pmod{30}$.

\begin{align*} x & \equiv 12 \pmod{25}\\ x & \equiv 2 \pmod{30} \end{align*} Hi guys, I'm not sure how to attack this problem. I know how to solve it if the moduli are coprime, but that ...
0
votes
2answers
38 views

If the squares of two integers are congruent $\bmod n$, the integers need not be

How do you prove $a^2 ≡ b^2 \pmod{n}$ does not imply $a ≡ b \pmod{n}$
3
votes
1answer
100 views

Why is modular inverse notation so ambiguous?

Consider $$\frac{a}{a}\pmod a,\ \ \ a\in\mathbb Z\setminus\{-1,0,1\}$$ There are two cases: $1)$ $\frac{a}{a}$ is the notation for the real number $1$. Then the expression is equivalent to $1$ ...
11
votes
2answers
86 views

Prove $x^5-2$ is irreducible over $\mathbb{Z}_{31}$

I am currently studying for my Algebra Qualifying Exam. I came across the following problem and am stuck on where to even begin: Prove that $x^5-2$ is irreducible over $\mathbb{Z}_{31}$. I have ...
1
vote
1answer
67 views

how to solve $x^2 \equiv a \pmod{ n}$, where $n = p_1 p_2 \dots p_r$

Let $p_1,p_2, \dots , p_r$ be different odd prime numbers, and $n$ be the multiplication of them $n = p_1 p_2 \dots p_r$. Let $$a \in \mathbb{Z} / n \mathbb{Z}$$ and assume that $\gcd(a,n)$ is ...
0
votes
4answers
65 views

Calculate the multiplicative inverse modulo a composite number

I want to calculate $ 8^{-1} \bmod 77 $ I can deduce $ 8^{-1} \bmod 77$ to $ 8^{59} \bmod 77 $ using Euler's Theorem. But how to move further now. Should i calculate $ 8^{59} $ and then divide ...
0
votes
1answer
23 views

modular arithmetic - congruency

Suppose $a$ is an integer, and $a\equiv 4 \pmod{13}$. Find the $c$ with $0\leq c \leq12$, and $c \equiv9a\pmod{13}.$ I'm mildly confused by this problem because I don't understand what the value ...
1
vote
0answers
59 views

Trying to find a quick method for $x! \pmod y$

I m trying to find a really quick method to calculate stuff like $x! \pmod y~~ \text{where }~\{x,y:\text{y is a prime}\}\in \mathbb{N}$ and $400\geq \{x,y\}\geq 50$ and $y>x+30$ $\text{Note : }$ ...
1
vote
0answers
30 views

Sequences of powers in different modulos, what orderings can we find in them?

The sequence $x, x^2, x^3, \dots , x^p$ in modulo $p$ seems kind of random. For example when $p = 23$ and $x=7$, we have 7, 3, 21, 9, 17, 4, 5, 12, 15, 13, 22, 16, 20, 2, 14, 6, 19, 18, 11, 8, 10, ...
1
vote
3answers
49 views

What are ways to solve Linear Congruences?

I am aware of something called the Chinese Remainder Theorem, using modulo inverses. For example, $$3x \equiv 17 \pmod{2014}$$ Instead of finding inverse modulo, How can I use the Chinese Remainder ...
2
votes
2answers
47 views

Modular Arithmetic with Multiple Exponents [duplicate]

I understand how to do modular arithmetic on numbers with large exponents (like $8^{202}$). However, I am having trouble understanding how to calculate something like: $ 3^{3^{3^{3^3}}}$ mod 5 ...
2
votes
1answer
32 views

How to prove a quadratic Diophantine equation has no solution?

Take the equation $3x^2-5y^2+7z^2 = 0$. If we take this $mod \: 4$ we get: $3x^2+3y^2+3z^2 \equiv 0 \: mod \: 4$ All of the squares modulo $4$ are either $0$ or $1$. $3x^2+3y^2+3z^2$ will never be ...
1
vote
2answers
48 views

Why does the Diophantine equation $2x^2\:-5y^2\:=\:1$ have no solutions?

I am trying to figure out why the equation, $2x^2\:-5y^2\:=\:1$ has no solutions. I have tried taking the equation mod $2$,$4$, and $5$, but when I do this I am not sure what I am supposed to look ...
1
vote
2answers
184 views

The congruence $(34\times 10^{(6n-1)}-43)/99 \equiv -1~\text{ or }~5 \pmod 6$

Trying to prove this congruence: $$ \frac{34\times 10^{(6n-1)}-43}{99} \equiv-1~\text{ or }~5 \pmod 6,\quad n\in\mathbb{N}$$ Progress Brought it to the form $$34\times 10^{6n-1}-43\equiv ...
1
vote
0answers
18 views

Proof: Let $\gcd(a,m)=1$. Then $a^i\equiv a^j\pmod{m}\iff i\equiv j\pmod{\text{ord}_m a}$

Would someone be so kind as to look over my proof for me? $\underline{\implies}$ EDITED Assume $a^i \equiv a^j\pmod m$. Then, $a^{i-j} \equiv 1 \pmod m$. This means that $i-j = k \cdot ...
6
votes
1answer
151 views

Prove that $13$ divides the number ${}^910 + 23$. [closed]

Prove that the number $13$ divides the number $\large \left( 10^{10^{10^{10^{10^{10^{10^{10^{10}}}}}}}} + 23\right)$.
0
votes
1answer
121 views

Why doesn't this congruence have solutions $x^2=83 \pmod{83^{2000}}$

Why doesn't this congruence have solutions $x^2=83 \pmod{83^{2000}}$ I know $x^2=83 \pmod{83}$ has a solution, I'm not sure how to show the above congruence doesn't though.
0
votes
3answers
213 views

Find the numbers that have an inverse modulo 11

I am trying to understand the inverse of a modulo. I want to find the numbers in the range 1,2,3...11 modulo 11 that has an inverse. I am confused and I can't understand how to identify which ...
7
votes
2answers
111 views

Do the last digits of exponential towers really converge to a fixed sequence?

While fooling around with exponential towers I noticed something odd: $$ 3^{3} \equiv 2\underline{7} \mod 100000 $$ $$ 3^{3^{3}} \equiv 849\underline{87} \mod 100000 $$ $$ 3^{3^{3^{3}}} \equiv ...
0
votes
1answer
34 views

Solving modular congruence

I have the following equation: $$-16 \equiv b \pmod {26}.$$ How do I calculate the value of $b$? I have forgotten elementary maths and want to refresh my concepts. Please explain to me how to solve ...
1
vote
3answers
102 views

If $n$ is an integer then $\gcd(2n+3,3n-2)=1\text{ or ?} $

There are two possible Gcd's for integers of the form, $2n+3$ and $3n-2$ I know the gcd is $1$ if I take the equation modulo $2$. However if I take the equation modulo $3$ I get, $2n$ and $-2$. ...
4
votes
4answers
79 views

What is the smallest positive integer of the form $30x+6y+10z$? [closed]

I am trying to find the smallest positive integer of the form $30x+6y+10z$, where $(x,y,z)\in\mathbb{Z}$ However, I do not know where to start. Hints or answers are welcome. Thanks!
1
vote
2answers
62 views

Is such modulus trick possible?

If we have a result of $a \pmod {10^{100} + 7}$ or $a \pmod {10^{100} + 1}$ without knowing what $a$ is, is there a way to get a result of $a \bmod 10^{100}$?
0
votes
1answer
33 views

Modular Congruence, Power

$(3x^2+2x+1)(4x^3+x^2+5x+1)=5x^5+4x^4+1\equiv 1 \pmod {x^4}$ Expanding the first part, I get $12x^5+11x^4+21x^3+14x^2+7x+1$. However, I do not understand how to get from the above statement to ...
11
votes
3answers
274 views

Finding $n$ satisfying $\{1^n-0^n,2^n-1^n,\cdots,p^n-(p-1)^n\}\equiv \{0,1,\cdots,p-1\}\pmod p$

Background : About a month ago, a friend of mine taught me his findings about a few polynomials which cover all the residue classes in mod $p$ where $p$ is a prime. Then, I began to consider the same ...
0
votes
1answer
35 views

Who to solve this linear modular equation system?

I have this equation system: a + b + c (mod 11) = 8 9a + 3b + c (mod 11) = 2 16a + 4b + c (mod 11) = 9 Unfortunately I totally don't know how to solve it. It is in general part of Lagrange's ...
2
votes
2answers
120 views

Changing the Modulo congruence base?

This is a conversion someone on SE made: $$77777\equiv1\pmod{4}\implies77777^{77777}\equiv77777^1\equiv7\pmod{10}$$ But I don't understand how this is done?
3
votes
2answers
111 views

Find the last digit of $77777^{77777}$

Find the last digit of $$77777^{77777}$$ I got a pattern going for $77777^n$ for $n=1, 2, ....$ to be: $$7, 9, 3, 1$$ for $n = 1, 2, 3, 4$ respectively. The idea is: $$77777^{77777} \pmod{10}$$ ...
-1
votes
1answer
28 views

Proof involving inverses and modulo

I'm working through an exercise which states: Let a' be the inverse of a modulo m and let b' be the inverse of b modulo m. Prove that a'b' is the inverse of ab modulo m. So far what I have is: We ...
0
votes
0answers
18 views

Modular Exponential non-coprimes

Given a,b,c,p so s.t p is Sophie-germain (p is prime and 2p+1 is prime). How would you solve: (a^b^c) mod (2p). I was thinking, if a is odd, I could use euler toitent function and calcular a^(b^c mod ...
0
votes
1answer
51 views

Why reduce $64\bmod{11}$ down to $12\bmod{11}$?

This is the problem I am currently working on Find this value: $(7^3\bmod{23})^2\bmod{11}$ Here's my work: $$\begin{align*} &(7^3\bmod{23})^2\bmod{11}\\ &64\bmod{11}=9 \end{align*}$$ This ...
2
votes
1answer
98 views

Finding remainder of dividing and moding large exponents [duplicate]

Can anyone explain how to calculate the remainder for types of problems like this: $2^{2131312213123}$ divided by 100 $13^{6601}$ mod 77
1
vote
0answers
44 views

What is the smallest number written as a sum of cubes?

What is the smallest number of the kind $\overline{999a}$, which can be presented as a sum of two natural cubes? ($a$ is a digit). I do NOT multiply below (when I write $999a$) $$999a = x^3 + y^3$$ ...
1
vote
0answers
51 views

Euler's totient function - Why?

I know this one's true, but I can't prove it. I've tried everything. $$a^{b\bmod{(\theta(m))}}\bmod(m)=a^b\bmod(m)$$ Multiply the exponent with $m-1$ (assume $m$ is prime, it doesn't matter anymore) ...
5
votes
2answers
116 views

Prove $717$ is not prime using Wilson's Theorem

Prove that $717$ is not prime using Wilson's Theorem. Assume $717$ is prime then: $$716! \equiv -1 \pmod{717}$$ $$ 716 \cdot 715! \equiv -1 \mod{717}$$ $$ 716 \equiv -1 \pmod{717}$$ $$715! = 715 ...
4
votes
0answers
187 views

Proving $11! + 1$ is prime

Prove that: $$11! + 1$$ is a prime number. Without computing the number (or factorial). Obviously, from Wilson's theorem, a number $n$ is prime if, $$(n-1)! + 1 \equiv 0 \pmod{n}$$ Since $n = ...
1
vote
1answer
59 views

Modular arithmetic - Power

I am dealing with the following question: Given a,b,c,d, p positive integers, I wanna compute a^(b^(c^d)) mod 2p+1. Given that p is sophie-germain. That is, 2p+1 is also prime. Any ideas?
1
vote
1answer
36 views

Let p be prime. Prove that:

Let p be prime: $p^2\choose p$ is congruent to p (mod $p^2$) and $2p\choose p$ is congruent to 2(mod$p^2)$ I know that when p is prime p|$p\choose k$ where $p\choose k$ can be defined as ...
1
vote
2answers
40 views

Modular arithmetic calculation $366^3\pmod {391}$ [closed]

$366^3\pmod{391}$ Is there an easy way to calculate this without a calculator?
1
vote
1answer
51 views

How many subgroups does $\mathbb{Z}_5$ have

How many subgroups does $\mathbb{Z}_5$ have (addition)? here is my Cayley table (sorry for the formatting): $\ \ \ 0\ 1\ 2\ 3\ 4\ \\ 0\ 0\ 1\ 2\ 3\ 4 \\ 1\ 1\ 2\ 3\ 4\ 0 \\ 2\ 2\ 3\ 4\ 0\ 1 \\ 3\ 3\ ...
2
votes
2answers
47 views

How is this a field?

From Stephen Abbott's - understanding analysis there is a section in the text which says: "The finite set $\{0,1,2,3,4\}$ is a field when addition and multiplication are computed modulo 5." I ...
3
votes
0answers
79 views

Prove $2^{1092}\equiv 1 \pmod {1093^2}$, and $3^{1092} \not \equiv 1 \pmod {1093^2}$

I did try to factorise 1092 and it is equal to $2^2*3*7*13$ and I really don't know what I can do with this. Do I need to calculate all the powers?
7
votes
1answer
127 views

Is The Statement $b^n\equiv 1\pmod n$ equivalent to “$x\mapsto b^x-x\pmod n$ is a bijection”?

Suppose that $n$ is a natural number and $b$ is one coprime to it such that $b^n\equiv 1\pmod n$. Does it follow that, if $b^x-x\equiv b^y-y\pmod n$, then $x\equiv y\pmod n$? This is inspired by ...
8
votes
3answers
172 views

Number Theory : What are the last three digits of $9^{9^{9^9}}?$

I was doing some basic Number Theory problems and came across this problem and was all thumbs : Find the last three digits of $9^{9^{9^9}}$ How would I go about solving this problem? I am a ...