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
4answers
158 views

“multiplicative inverse in the modulo of the larger number” what does that mean?

while I was reading this artical I have read the following paragraph: The interesting thing is that if two numbers have a $\gcd$ of $1$, then the smaller of the two numbers has a multiplicative ...
20
votes
13answers
2k views

Why do we use “congruent to” instead of equal to?

I'm more familiar with the notation $a \equiv b \pmod c$, but I think this is equivalent to $a \bmod c = b \bmod c $, which makes it clear that we should put a $=$ instead of $\equiv$. What's the ...
-1
votes
4answers
32 views

What is a modular inverse?????

I realize that this question has been asked before; please just bear with me. I looked across the Internet on here, Khan Academy, and many other sites in order to understand what an inverse mod is and ...
2
votes
4answers
51 views

Modular maths: How do I find the remainder?

How do I find the remainder of $5^{22} \pmod{25}$? And also how do I find the remainder of $3^{16} + 7 \pmod{5}$?
0
votes
1answer
84 views

$x^2 + 6y^2 = 2807$ no integer solution

Prove that equation $x^2 + 6y^2 = 2807$ doesn't have solution in the set of integers. Obviously $x^2$ is odd, so $x$ is odd. Then, I taught that every perfect square has the rest $1$ or $3\bmod ...
0
votes
1answer
32 views

Modulo of squared number

I have tested a lot of combinations with integer numbers and it seems like we can say that $y^2 \bmod n$ equals $((y \bmod n)^2) \bmod n$. I can't find any resource that acknowledges this. Is my ...
0
votes
0answers
42 views

$x^2 + y^2 + z^2 = 2007^{2011}$ with $x$, $y$ and $z$ integers [duplicate]

Solve the equations $x^2 + y^2 + z^2 = 2007^{2011}$ in the set of integers.
0
votes
0answers
28 views

Sum over product of residues modulo two different bases

Let $M(x,y)$ be a modulo function. Specifically, $$ M(x,y) = \begin{cases} x, & \text{when } -\lfloor \frac y2\rfloor \leq x \lt \lfloor \frac y2\rfloor \\ M(x-y,y), & \text{when } x \geq ...
0
votes
1answer
43 views

$p^3 = 2009 + 47 * 2^q$ where p and q are primes

Solve the ecuations $p^3 = 2009 + 47 * 2^q$, where $p$ and $q$ are primes. Fermat's little theorem could help.
2
votes
2answers
70 views

Remainder of division of ${6}^{7^n}$ to $43$

What is the Remainder of the division of ${6}^{7^n}$ to $43$? I've tried with Fermat's little theorem, but it haven't work. Update : lab bhattacharjee gave a nice proof. But I want to know if ...
3
votes
6answers
82 views

$\frac{7}{5} \equiv 11 \pmod{12}$. Why is it $11$?

I know this equation is true but I don't get the reason $\frac{7}{5}$ is congruent to $11$ here. The quotient is supposed to be $1.4$ in non modular arithmetic and I don't get where $11$ has come ...
1
vote
1answer
21 views

To show that H,K are sub-groups of G (U36)

$G\:=U_{36}$ $$H=\left\{\left[x\right]\in U_{36}\::\:x\equiv 1\left(mod4\right)\right\}$$ $$K=\left\{\left[y\right]\in U_{36}\::\:y\equiv 1\left(mod9\right)\right\}$$ I need to show that H,K are ...
0
votes
1answer
28 views

How do I solve this system of residue class equations?

$$\overline{3}x+\overline{2}y=\overline1$$ $$\overline{5}x+y=\overline4$$ both in $\Bbb{Z}_7$ So I multiple the second by 2 to get $\overline{10}x+\overline2y=\overline8$. Then I subtract the first ...
0
votes
1answer
29 views

Finding Numbers where modulo is k

I have given a number $A$ where $1\le A\le 10^6$ and a number $K$. I have to find the all the numbers between $1$ to $A$ where $A\%i=k$ and $i$ is $1\le i\le A$. Is there any better solution than ...
1
vote
3answers
67 views

Question about congruence modulo n

Is there any sort of algorithm to calculate the remainder when $10^{515}$ is divided by $7$? Could the same algorithm be applied to finding the remainder of $8^{391}$ divided by $5$? Is it even ...
1
vote
1answer
36 views

Solve the system of congruences (CRT)

$$560x \equiv 1 \pmod{3, 11, 13}$$ I found a few (by trial and error) $560x \equiv 1 \pmod{13} \implies x = 1 + 13k$. $560x \equiv 1 \pmod{3} \implies x = 2 + 3k$. $560x \equiv 1 ...
5
votes
4answers
144 views

How do I find the remainder of $4^0+4^1+4^2+4^3+ \cdots + 4^{40}$ divided by 17?

Recently I came across a question, Find the remainder of $4^0+4^1+4^2+4^3+ \cdots + 4^{40}$ divided by 17? At first I applied sum of G.P. formula but ended up with the expression $1\cdot ...
-2
votes
1answer
18 views

Excel: calculating the number of months left in school year [closed]

School years, in many places, begin in September. Here we can, crudely, assume the number of months left in a school year would be 12 in September and 1 in August. My formula in Excel is like this: ...
2
votes
1answer
22 views

Calculate the modular inverse of $2a$ given that of $a$

My problem is that I have to calculate some modular inverses of numbers that are related by multiplying by $2$, that is: Given $a$ and $x$ so that $ax\equiv1\mod n$ ($n$ being an odd number) I need ...
1
vote
3answers
68 views

last two digits of $14^{5532}$?

This is a exam question, something related to network security, I have no clue how to solve this! Last two digits of $7^4$ and $3^{20}$ is $01$, what is the last two digits of $14^{5532}$?
0
votes
5answers
85 views

how to solve $2^x \bmod 53 ≡ 1$?

I was writing network security exam, one of the question is $2^x \bmod 53 ≡ 1$ where x is a non-zero integer. This they asked because most of the encryption and decryption algorithms involves modulus ...
5
votes
1answer
206 views

Wilson's Theorem - Why only for primes? [closed]

Why is it true that Wilson's Theorem only holds for prime numbers? I read a proof of it, and it did not seem to cater to that aspect of the theorem.
0
votes
0answers
32 views

Minimizing a sum given variables

I have this expression $$ax - b\left\lfloor\frac{cx}{m}\right\rfloor$$ Variables $a, b, c, m$ are known/given positive integers, and $x$ is an unknown integer with bounds $1 \leq x \leq m-1$. I ...
0
votes
0answers
49 views

Solutions to ax = by mod m?

Given congruence $ax = by \bmod m $ for known integers $a,b,m$, with $m $ composite, can this relation be simplified or solved?
3
votes
2answers
58 views

If $x^a \equiv x^b \bmod p$, what can we say about $a$ and $b$?

If $x^a \equiv x^b \bmod p$, what can we say about $a$ and $b$, for $p$ prime? Is there any way to show the relationship between $a$ and $b$ specifically? It doesn't seem to be the case that $ a ...
0
votes
5answers
88 views

Deriving Euler's theorem from Fermat's little theorem

I would like to know why $a^p \equiv a \pmod p$ is the same as $a^{p-1} \equiv 1 \pmod p$, and also how Fermat's little theorem can be used to derive Euler's theorem, or vice versa. Please keep in ...
1
vote
1answer
34 views

Why is $2^4$ congruent to $-1$ modulo $17$?

I saw an interesting question on Quora (What remainder is obtained when $2^{2017}+1$ is divided by $17$?), but I do not understand the author's solution: Three, because $$ \begin{align} 2^{2017} ...
1
vote
2answers
24 views

Computing a remainder of big numbers using modular arithmetic

I have a kind of confusion dealing with modular arithmetic, specially regarding remainders. I am aware of Euler/Fermat theorem that says: if p is prime, then 2^(p-1) is congruent to 1 module p. ...
1
vote
2answers
185 views

How come $\ n\ $ always divides at least one of the item of the sequence?

Given positive integer$\ \displaystyle n,\ $ the sequence is: $\displaystyle 2^n$ $\displaystyle 2^n - 2^{n-1}$ $\displaystyle 2^n - 2^{n-1} + 2^{n-2}$ $\displaystyle 2^n - 2^{n-1} + 2^{n-2} - ...
1
vote
2answers
49 views

To calculate the remainder of (111…) + (222…) + (333…) + (444…) + (555…) + (666…) +(777…) by 37

To Evaluate the remainder Question: $ (111...) + (222...) + (333...) + (444...) + (555...) + (666...) +(777...)$ mod $37$ In each bracket, the single digit $(1, 2, 3, ..., 7)$ is written $110$ ...
0
votes
0answers
89 views

Non-linear system of modular arithmetic equations

Is there an efficient algorithm to solve the following system of equations? $\begin{array}{ccccc} \begin{array}{c} us_{1}^{2}+vt_{1}^{2}=a_{1}\pmod p\\ us_{2}^{2}+vt_{2}^{2}=a_{2}\pmod p\\ \vdots\\ ...
0
votes
1answer
21 views

Modular Arithmetic - Approaching this type of problems

For my upcoming exam in Algorithms, as part of Cryptography, we are supposed to be able to solve these types of questions. I don't have the notes from that lecture, so I'm finding it difficult to ...
6
votes
1answer
120 views

FRACTRAN for natural numbers

Is there a simple analogue of FRACTRAN that maps a natural number to a natural number, instead of mapping a list of fractions to a natural number? One could use Gödel encoding to translate FRACTRAN ...
2
votes
2answers
37 views

Remainder Dividing Repunits

If $n = 11111 \ldots 1$ (1 repeated 123 times.) Then find the remainder when $n$ is divided by 271? I know I can write this in the form of a sum of a gp but it doesn't help to find the remainder... ...
1
vote
0answers
67 views

Find the number of “p-safe numbers”

For a positive integer $p$, define the positive integer $n$ to be $p$-safe if $n$ differs in absolute value by more than $2$ from all multiples of $p$. For example, the set of $10$-safe numbers is ...
-2
votes
2answers
50 views

How to find $x$ value such that $x^5\equiv 99 \pmod{21}$ using congruences [closed]

I know congruences somewhat, however this problem is troubling me a lot. Please help me. If $17^5\equiv 5 \pmod {21}$, then at what value of x, $x^5\equiv 99 \pmod{21}$? High regards, ZION
0
votes
4answers
120 views

How many $0$s does the number $30!$ have? [duplicate]

I want to find out the number of $0$s in the number $30!$, what should I do? Is there any trick that would work for a general question of this type, like number of $0$s in $50!$ ?
2
votes
2answers
57 views

Fibonacci Cyclic Pattern [duplicate]

I want to show the Fibonacci numbers are cyclic in mod n. I have tried some small values for n and I can see this is the same. In terms of a proof, I'm thinking of using the pigeonhole principle of ...
0
votes
1answer
29 views

How to prove that $(a-b) \mod N = a \mod N + ((-b) \mod N)$?

I've gone through the similar post Modulo of a negative number . But that post is not about proof and I'm asking for the proof in general. This question is another follow up question of my previous ...
0
votes
1answer
43 views

Chinese Remainder Theorem example

$$x = 4 \bmod 18$$ $$x = 52 \bmod 96$$ $$x = 6 \bmod 20$$ My current algorithm thinks the answer is $x \equiv 1066 \bmod 1440$ but I don't think there should be a solution to this. The algorithm: ...
1
vote
1answer
43 views

Congruence using extended GCD

$$\eqalign{ x &\equiv 5 \mod 15\cr x &\equiv 8 \mod 21\cr}$$ The extended Euclidean algorithm gives $x≡50 \bmod 105$. I understand now that if we combine the two it implies ...
1
vote
2answers
49 views

Why is this congruence true?

$$\eqalign{ x &\equiv 5 \mod 15\cr x &\equiv 8 \mod 21\cr}$$ The extended Euclidean algorithm gives $x≡50 \bmod 105$. How/why? I am trying to understand how this is true when ...
0
votes
0answers
40 views

A residue question in integers

Given $N\in\Bbb N$, is it possible to find $9$ positive integers $A_j,N_i$ with $j\in\{1,2,3\}$, $i\in\{1,2,3,4,5,6\}$ such that following holds? $(1)$ $N\log N < A_j < cN\log N$ at every $j$ ...
14
votes
7answers
1k views

Why do remainders show cyclic pattern?

Let us find the remainders of $\dfrac{6^n}{7}$, Remainder of $6^0/7 = 1$ Remainder of $6/7 = 6$ Remainder of $36/7 = 1$ Remainder of $216/7 = 6$ Remainder of $1296/7 = 1$ This pattern of ...
0
votes
0answers
24 views

Is there a solution to this problem on Fermat's Quotient?

We define Fermat's Quotient as $q_a = (a^p-1)/p \pmod p $ where $p$ is a prime greater than $2$. How will you prove that the only solutions of the equation $q_a=0$, $q_b=0$ and $q_{a+b}=0$ where ...
1
vote
0answers
19 views

Need my CRT work spot-checked

So I have a bunch of equations that look like this: $$k + tx \equiv a \bmod m$$ Where $t$ is the common variable I am solving for among the equations (each equation may have different values for ...
1
vote
2answers
28 views

Modular Quadratic Equation

I'm trying to solve that equation: $x^2-3x-5\equiv0\pmod{343}$ I've completed the square as follows: $x^2-3x-5 \equiv x^2+340x-5\equiv(x+170)^2-170^2-5\pmod{343}\\ (x+170)^2 \equiv 93\pmod{343}\\ ...
0
votes
2answers
47 views

Use proof by contradiction to prove that if $a$ and $b$ are odd integers, then $4 \nmid (a^2+b^2)$.

I have been working through the following proof: Use proof by contradiction to prove that if $a$ and $b$ are odd integers, then $4 \nmid (a^2+b^2)$. Below, I have included screenshots of the ...
0
votes
3answers
52 views

Chinese remainder theorem for three equations?

Is there a straightforward approach for solving the Chinese Remainder Theorem with three congruences? $$x \equiv a \bmod A$$ $$x \equiv b \bmod B$$ $$x \equiv c \bmod C$$ Assuming all values are ...
2
votes
0answers
34 views

How do I interpret “K2 mod K1”?

I've been doing a bit of work these past couple of nights on computing cyclic subspace decompositions, finding cyclic bases, and then computing the Jordan canonical form of matrices. My question is: ...