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
16 views

Change modulus in modular inversion

There exists a property of congruences that allows changing the modulus in a modular inversion calculation? For example: Been $a \equiv b^{-1} \mod n$, is there a way to calculate $a$ knowing $b$ ...
0
votes
0answers
14 views

What's wrong with my congruence simplification? $ax \equiv by \bmod m$

Here is my work in an attempt to simplify. $a,b,m$ are known non-negative integers. $$ax \equiv by \bmod m$$ Step 1: Let $g = \gcd(a,b,m)$. Let $a_1 = a/g$, and $b_1 = b/g$, and $m_1=m/g$, then ...
1
vote
5answers
62 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$. This they asked because most of the encryption and decryption algorithms involves modulus calculation
5
votes
1answer
180 views

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

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
23 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
46 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
56 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
68 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
30 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
128 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
38 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
21 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
20 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
104 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
31 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
63 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
113 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
52 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
24 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
40 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
35 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
23 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
18 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
43 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
50 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 ...
-1
votes
0answers
7 views

Question on equivalent statement of wolstenholme's [closed]

Wolstenholme's was mentioned as equivalent to stating that ${a \choose b} \equiv {pa \choose pb} \mod p^2$. I don't see how this works, can anyone explain it to me? Thanks
-2
votes
0answers
20 views

mapping of integer to unit circle through function $f(k)=k\theta \pmod{2\pi}$ [closed]

Let $N$ be a positive integer and $\theta$ an angle in $(0,2\pi)$. Consider the map $f\colon\{0,1,\ldots,N\}\to\text{unit circle}$, defined by $f(k)=k\theta \pmod{2\pi}$. Show that the image of $f$ ...
2
votes
0answers
32 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
26 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
18 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) ...
-4
votes
1answer
40 views

A system with modular arithmetic [closed]

How do I solve this system? Note: (y mod 10) = (x mod 10). $$\begin{cases} 2y - x + (x \bmod 10) = 42\\[1ex] y + (x \bmod 10)= 32 \end{cases}$$ for x and y?
1
vote
1answer
43 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
25 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$ ...
2
votes
4answers
89 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
65 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 ...
0
votes
2answers
21 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
28 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 ...
0
votes
4answers
35 views

How can I calculate these large exponents with mods?

Is there a fast technique that I can use that is similar in each case to calculate the following: $$(1100)^{1357} \mod{2623} = 1519$$ $$(1819)^{1357} \mod{2623} = 2124$$ $$(0200)^{1357} \mod{2623} ...
3
votes
1answer
45 views

Finding period of a recursive sequence defined by modular operator?

If $f(x)$ is defined as : $f(x)=i$ ,if $x\equiv i$ (mod n), $0\leq i< n$ How can I prove whether the following recursive sequences are periodic or not? ...
2
votes
2answers
82 views

From a silly (long division) puzzle comes an interesting number-theory “theorem” (quotes indicate some doubt).

I've worked a BUNCH of this type of long division puzzle. EDIT (The problem represents LOELPE/MNTN where EP is the quotient and LEAC is the remainder, with LIONP representing E times MNTN, PPMC ...
1
vote
2answers
63 views

Modulus and Fermat's Little Theorem

How do I calculate $ 11^{23} \bmod{163} $ using fermat's little theorem ?
1
vote
1answer
61 views

Solve $n(n+1) \equiv 0 \pmod{1004}$

Solve: $$n(n+1) \equiv 0 \pmod{1004}$$ For the smallest possible $n > 0$. It's either $n \equiv 0$ or $n \equiv -1 \pmod{1004}$. The correct answer is $251$, I'm not sure how though.
3
votes
1answer
56 views

Does $(a^p + b^p)^{p-1} \equiv 1 \pmod {p^2}$ have any solutions where $a$ and $b$ are co-primes less than $p$?

How will you prove that $(a^p + b^p)^{p-1} \equiv 1 \pmod {p^2}$ has no solution where $p$ is a prime number and $a$, $b$ are two co-primes less than $p$? If this equation has a solution, then what it ...
25
votes
1answer
292 views

Fibonacci $\equiv -1 \mod p^2$

Is there a prime $p > 3$ such that the Fibonacci number $F_{np} \equiv -1 \mod p^2$ for some natural number $n$? I know none of the first $1000$ primes $> 3$ qualify. EDIT: In response to ...