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
1answer
90 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 6$,...
0
votes
1answer
50 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
1answer
50 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
79 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 this ...
3
votes
6answers
85 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
49 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 sub-...
0
votes
1answer
35 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
31 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
2answers
140 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
61 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
158 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 \dfrac{...
2
votes
1answer
24 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
110 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
139 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 ...
7
votes
1answer
260 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.
1
vote
1answer
42 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
54 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
62 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
111 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
38 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
28 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
207 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} - 2^{...
1
vote
2answers
178 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
118 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
27 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
149 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
89 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
80 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
73 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
155 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
92 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
92 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
58 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
47 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
58 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 ...
13
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 $1,6,1,6...$...
0
votes
0answers
26 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 $(a,p)...
1
vote
0answers
22 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 $k,...
1
vote
2answers
36 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}\\ y^...
0
votes
2answers
95 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
147 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
41 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: ...
0
votes
1answer
33 views

In a modular arithmetic equation, how to find 'a' given a range?

Say I have an equation in the form $$a\bmod b = c$$ I know $b$ and $c$ I'm given a range $(d,e)$ (where $d$ and $e$ are integers). How can I find all values of $a$ that satisfy the inequality $d \...
2
votes
0answers
29 views

A stochastic variant of the heat equation modulo $2\pi$ has weird unstable particle-antiparticle solutions. Does this equation have a name?

I implemented a discretization of a weird 2D heat equation "mod $2\pi$", $$\dot{f}(\mathbf{x},t)=\Delta^*f(\mathbf{x},t)$$ where (WARNING: handwavy, I'm not sure I understand it) $\Delta^*=\nabla^*\...
1
vote
1answer
48 views

How many solutions for $(6b)^b\equiv (12b-k)^b\mod p$?

Rephrasing my previous question; If $(6b)^b\equiv (12b-k)^b\mod p$, where $b$ is odd and $p=1+6qb$, and where $p$ and $q$ are prime, are there any solutions for $k$ other than $k\equiv6b\mod p$?
0
votes
1answer
33 views

Proving B Congruent C given AB congruent AC

This is a very trivial question, i seem to have arrived at a proof for an excercise but the proof just doesn't feel.. right. It is too small and simple. The fact to be proved is that if $AB\equiv AC$ ...
3
votes
4answers
99 views

If $a^b\equiv c^b\mod p$, can we conclude that $a\equiv c\mod p$?

If $a^b\equiv c^b\mod p$, is is true that $a\equiv c\mod p$, where $b$ is odd and $p$ is prime? We know that if $a\equiv c\mod p$, then $a^b\equiv c^b\mod p$. Is the reverse true?
1
vote
2answers
87 views

Prove that there are infinitely many composite numbers of the form $2^{2^n}+3$.

There are infinitely many composite numbers of the form $2^{2^n}+3$. [Hint: Use the fact that $2^{2n}=3k+1$ for some $k$ to establish that $7\mid2^{2^{2n+1}}+3$.] If $p$ is a prime divisor of $2^{...
0
votes
2answers
24 views

Modular arithmetic exponentiation

Does modulus apply to exponents as well. eg Let $ xy \equiv 1 (mod\;m).$ then does $a^{xy} \equiv a^{1} (mod\;m)$ ?
0
votes
0answers
41 views

Exponential cryptosystem

The cryptosystem works as follows: The plaintext message is first replaced by ciphers (a=00, b=01, etc.) and then encrypted in blocks of four digits. So if the message is "hi", the plaintext number ...