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
8 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
18 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 ...
0
votes
0answers
22 views

Reducing list $5,5,10,…,5(p - 1) / 2$ to numbers between $-(p - 1)/2$ and $(p-1)/2$ where p is prime

I have noticed that if I choose a prime p of a form $10k + 1$, make a list $5, 10, 15, ..., 5(p-1)/2$ and reduce each term $\pmod{p}$ to get values between $-(p-1)/2 $ $and$ $(p-1)/2$, I get an ...
3
votes
0answers
33 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
30 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
61 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
49 views

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

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
112 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
34 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
42 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
49 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 [on hold]

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}$ [on hold]

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
31 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
88 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
44 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
80 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
289 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 ...
0
votes
1answer
58 views

Calculate $2^n \pmod{14^8}$ with large numbers quickly

Is there a way to calculate $2^n \pmod{14^8}$ faster than binary exponentiation? The $n$ values in question are very large, for example $2^{65536}$, and the calculations have to be done around $14^8$ ...
2
votes
2answers
46 views

Wilson's theorem

According to Wilson's theorem, when p is prime (p-1)! mod p = -1 or p-1 What's the remainder in cases of (p-2)! mod p or ...
1
vote
5answers
72 views

Mod question: $-5 \pmod 3$?

How come $-5 \equiv 1 \pmod 3$ and not $-5 \equiv 2\ $ or $\ -2 \pmod{3}$? $-\frac{5}{3}= -1 -\frac{2}{3}$. i.e. Remainder is $-2$ or $2$?
3
votes
4answers
2k views

Calculate 2000! (mod 2003)

Calculate 2000! (mod 2003) This can easily be solved by programming but is there a way to solve it, possibly with knowledge about finite fields? (2003 is a prime number, so mod(2003) is a finite ...
2
votes
3answers
59 views

Problem in proof of Chinese remainder theorem, and applying it.

Please don't mark it as duplicate. First read the whole question. So Chinese Remainder Theorem states that,: Let $n_1,n_2,...,n_k$ be $k$ positive integers which are pairwise relatively prime. If ...
0
votes
1answer
24 views

Multiplicative inverse of polynomial modulus an integer

How do you calculate the multiplicative inverse of a polynomial mod a monomial/integer?The specific questions are: Find the multiplicative inverse of 1) x+1 mod 3 2) x^2+x-1 mod 3 3) x^2+x-1 mod 32 I ...
1
vote
1answer
37 views

Cycles in the Fibonacci Sequence mod n with matrices

I was just looking at this question about Fibonacci sequence cycles modulo 5, and I happened to see a very nice solution that involved using matrices. Using the matrix representation of the Fibonacci ...
2
votes
1answer
39 views

Closed-Form Modular Arithmetic

Is there a way to define modulo division (or functions of modular arithmetic in general) as superposition of (elementary?) functions? For example, the multiplication is first introduced as ...
37
votes
13answers
5k views

How to prove that the Fibonacci sequence is periodic mod 5 without using induction?

The sequence $(F_{n})$ of Fibonacci numbers is defined by the recurrence relation $$F_{n}=F_{n-1}+F_{n-2}$$ for all $n \geq 2$ with $F_{0} := 0$ and $F_{1} :=1$. Without mathematical induction, ...
3
votes
1answer
27 views

Modular arithmetic: $P \cdot Q^{-1} \mod p$

I am reading an explanation to a programming competition, where one of the step is to calculate $P \cdot Q^{-1} \mod p$, where p is a prime. I was always doing this by calculating multiplicative ...
1
vote
1answer
24 views

Rules for modulo of bitwise xor

There are rules for modulo operation involving summation, multiplication and division. For example: ...