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

0
votes
0answers
26 views

sequence of primes satisfying a particular equation

Do this equation have other solutions other than $P(52)=241$; $3^{5+7+11+13+\cdots+P(n-3)+P(n-2)}=P(n-1) \mod{P(n)}$. Here $P(n)$ is the $n$-th odd prime. I have checked $n$ up to $5500$, but I ...
-1
votes
0answers
47 views

Factorial Formula $1\cdot1! + 2\cdot2! + \cdots + x\cdot x! = (x+1)!−1$

The following relation can be easily proved with the help of Mathematical Induction $$1\cdot1! + 2\cdot2! + \cdots + x\cdot x! = (x+1)!−1$$ However, for large value of $x$ the result may escalate ...
0
votes
2answers
28 views

In (m mod n = x) how to find m when you know n and x?

So I'm doing some cryptography assignment and I'm dealing with a modular arithmetic in hexadecimal. Basically I have the values for $n$ and the remainder $x$, but I need to find the original number ...
1
vote
1answer
44 views

Irrationality proof trick with Mod [duplicate]

You will see here: Bill Dubuque's Slick $\sqrt{3}$ irrationality proof What is the trick with modulus for proving irrationality? What about $\sqrt{2}$ Can you prove this is irrational by that ...
-1
votes
0answers
21 views

Shortcut to mod an integer that repeats a subnumber? [on hold]

For example, 556755675567 or 45454545 or 114114. Given a random integer, is there an algorithm to follow that will properly mod these types of numbers? I have noted that it can be factored into ...
0
votes
0answers
21 views

Remainder of a number raised to a large exponent, when the exponent itself is raised to a large exponent

I know how to find the remainder of a number raised to a large exponent, for example, $3^{348}$ in modulo 2 will simplify to $1^{348}$ and therefore 1 in modulo 2, since 3 is congruent to 1 modulo 2. ...
0
votes
1answer
17 views

Find all solutions to the congruence relation

Let $p$ be a prime and $d$ is a divisor of $p-1$ Let $a$ be an integer that is not divisible by $p$, and suppose $a$ has order $d \pmod p$. List all solutions to $x^d -1 \equiv 0\pmod p$ My attempt ...
0
votes
4answers
39 views

Is there an integer $x$ where $(0 \leq x < 19)$ such that $x ≡ 123^{12345} \pmod {19}$?

I'm working on a questions which says: Is there an integer $x$ where $(0 \leq x < 19)$ such that $x ≡ 123^{12345} \pmod {19}$? I got an answer of $18$ mod $19$, though I'm not sure whether ...
7
votes
4answers
92 views

Show $17$ does not divide $5n^2 + 15$ for any integer $n$

Claim: $17$ does not divide $5n^2 + 15$ for any integer $n$. Is there a way to do this aside from exhaustively considering $n \equiv 0$, $n \equiv 1 , \ldots, n \equiv 16 \pmod{17}$ and showing $5n^2 ...
1
vote
1answer
45 views

Finding the inverse modulo . $7^{-2}\pmod {11}$ and $7^{-3}\pmod {11}$

$7^{-1}\pmod{11}$ the above can be found by $7x\pmod{11}\equiv 1$ and $x=8$ now i am confused on how to find $7^{-2}\pmod{11}$ and $7^{-3}\pmod{11}$ .
5
votes
2answers
34 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
132 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
35 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
16 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
29 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
43 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
34 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}$
2
votes
1answer
83 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
72 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
66 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
33 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
22 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
53 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
20 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
45 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
35 views

Modular Arithmetic with Multiple Exponents

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
27 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
46 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
91 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
17 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 ...
4
votes
1answer
92 views

Prove that $13$ divides the number $\large 10^{10^{10^{10^{10^{10^{10^{10^{10}}}}}}}} + 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
39 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
202 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 ...
6
votes
2answers
71 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
31 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
59 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$. ...
2
votes
4answers
64 views

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

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
61 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
27 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 ...
2
votes
0answers
78 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
27 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
103 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
96 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
23 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
16 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
41 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
43 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
48 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) ...