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
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 ...
0
votes
4answers
54 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} =...
4
votes
1answer
140 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? $$x_{i+1}=f(k_0+k_1x_{i}+k_2x_{i-1}+...+...
2
votes
2answers
103 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
85 views

Modulus and Fermat's Little Theorem

How do I calculate $ 11^{23} \bmod{163} $ using fermat's little theorem ?
1
vote
1answer
64 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.
4
votes
1answer
65 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 ...
27
votes
2answers
860 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
91 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
130 views

Wilson's theorem

According to Wilson's theorem, when $p$ is prime $$(p-1)! \equiv p-1 \mod p$$ What's the remainder in cases of $$(p-2)! \mod p$$ or $$(p-3)! \mod p$$ Can these be solved using Wilson's theorem ...
0
votes
5answers
74 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$?
2
votes
3answers
2k views

Which day of the week will be $100$ days from now

If today is Wednesday, what day of the week will it be $100$ days from now? Going forward $1,8,15,\dots,92,99$ days all result in Wednesday. So the $100$th day will be Thursday. But the solution ...
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
95 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
92 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
88 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
2answers
82 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 summation,...
39
votes
13answers
6k 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
44 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
84 views

Rules for modulo of bitwise xor

There are rules for modulo operation involving summation, multiplication and division. For example: ...
1
vote
0answers
39 views

Modular fractions: $5 \big| 3- \frac 12$

I've read a lot here about how modular fractions are valid as long as the denominator is invertible, but they always cause me trouble understing this part: From the definition of congruence: $$ a \...
2
votes
2answers
103 views

How can I simplify $123^{11} \mod 323$?

I am busy studying the RSA cryptosystem and would like to know how to simplify things like this: $123^{11} \mod 323$
2
votes
1answer
75 views

Congruence of 2 fractions—how to properly rewrite in terms without modulo?

EDIT: Following Theo's comment, the equivalence holds since one can (must) rewrite $1/a$ as $(1+23k)/a$. Provided that $$\frac{1}{25} \equiv \frac{1}{2}\pmod {23}$$ is true, why can I not rewrite ...
1
vote
0answers
46 views

What are modulos and how would I be able to use them to solve questions regarding the last digit of a raised power?

When given questions like "What is the last digit of the result to 3^56?", I usually look for a recurring pattern involving smaller powers of 3. In this question for example, the recurring pattern for ...
1
vote
1answer
26 views

$a\cdot(b^{-1}\bmod m)$ Can be be solved using modular multiplication

Does $a\cdot(b^{-1}\bmod m) = (a\bmod m) \cdot(b^{-1}\bmod m).$ where $\bmod$ represents remainder left on division with $m$. $b^{-1} \bmod m$ is multiplicative inverse.
6
votes
4answers
1k views

Last 10 digits of the billionth fibonacci number?

I want to compute the last ten digits of the billionth fibonacci number, but my notebook doesn't even have the power to calculate such big numbers, so I though of a very simple trick: The carry of ...
0
votes
2answers
44 views

If $g$ is a primitive root modulo $p$, then $(p-1)! \equiv g^{p(p-1)/2} \pmod{p}$

Does anyone know how to prove the following theorem: If $g$ is a primitive root modulo $p$ (and $p$ is a prime number), then $$(p-1)! \equiv g^{p(p-1)/2} \pmod{p}.$$
0
votes
1answer
32 views

The solutions to $x^m \equiv 1 \bmod p$ will all be solutions to $x^{mn} \equiv 1 \bmod p$ for any $n$.

Can you please show the proof of "The solutions to $x^m \equiv 1 \bmod p$ will all be solutions to $x^{mn} \equiv 1 \bmod p$ for any $n$."
0
votes
0answers
27 views

subsets with predefined sequences

I have a set $N=\{m,m+1,m+2,...,n\}$ And there are some generating functions of the format : $f(x,k) = (x^2 -1) \mod k$, where $k \le \sqrt m$ and $k$ is in the form $(6i+1)$ or $(6i-1)$, $\forall ...
0
votes
0answers
39 views

Rabin's cryptography - when the message $M$ isn't coprime to $n = pq$

Say the message $M$ is a product of one of the primes $p$ or $q$, won't the $gcd$ of $M$ and $n$ (the public encryption key) give me $p$ or $q$? say $p = 11$ $q=19$ $n=11*19=209$ and $M=33$. $gcd(33,...
2
votes
2answers
379 views

Fermat's little theorem

This is a very interesting word problem that I came across in an old textbook of mine. So I mused over this problem for a while and tried to look at the different ways to approach it but unfortunately ...
1
vote
1answer
50 views

polynomial modulo for higher degree

Given $f(x) , n, g(x)$ where $g(x)$ is usually of a small degree then if we find $h_1(x)$ such that $f(x)\equiv h_1(x)\mod \{n,g(x)\}$ , Is there any algorithm to find $h_2(x)$ such that $f(x)\equiv ...
2
votes
4answers
141 views

An easy way to calculate $12^{101} \bmod 551$?

We learn about encryption methods, and in one of the exercises we need to calculate: $12^{101} \bmod 551$. There an easy way to calculate it? We know that: $M^5=12 \mod 551$ And $M^{505}=M$ ($M\in \...
0
votes
4answers
108 views

What is the function “mod”

Surfing this site, I have often seen many functions and expressions involving $\bmod$ and I have no clue about its meaning. What does that $\bmod$ mean?
0
votes
4answers
94 views

Units digit when there is a power of power

How do you find the units digit in case of an expression like this $$ 7^{8^7} $$ I know how to find the units digit when there is one integer and there is only one power. But how do I find it when ...
0
votes
4answers
46 views

How to manually determine big number congruences

How is it possible to determine if the the following congruence is true manually, with resort to a basic calculator? The real problem here is how to do the math with a such big number? $$ 2015^{50} \...
4
votes
1answer
110 views

Find the remainder when the sum is divided by $1000$

Find $S \pmod{1000}$ given: $$S = \sum_{n=0}^{2015} n! + n^3 - n^2 + n - 1$$ $$S_0 = 0! + 0 - 0 + 0 -1 = 0$$ $$S_1 = 1! + 1 - 1 + 1 - 1 = 1$$ $$S_2 = 2! + 8 - 4 + 2 - 1 = 7$$ This isn't helping, ...
1
vote
1answer
42 views

Polynomial function residues

If we use Euclid's representation for integers $n=aq+r$, we can write $n\equiv r \mod q$. We can also write functions similarly, for example $n(x)=a(x)q(x)+r(x)$ and so I imagine we can write $n(x)\...
0
votes
0answers
21 views

One dimensional representations of $SL_2(\mathbb{Z}/n\mathbb{Z})$

Someone knows a reference or knows how to calculate the linear character of $SL_2(\mathbb{Z}/n\mathbb{Z})$, for an arbitrary $n$? Thanks
1
vote
4answers
60 views

system of modular equations.

$x\equiv 2\pmod3$ $x\equiv 3\pmod 5$ $x\equiv 7 \pmod{11}$ How can I solve this system for $x$? I've tried all kinds of things using divisibility but no success. Any hints of solutions are greatly ...
1
vote
3answers
61 views

Smallest divisible repunits

A repunit of length k is a number containing k ones (1, 11, 111...). R(k) is defined to be the repunit of length k. A(n) is the least value of k such that R(k) is divisble by n (assuming gcd(n, 10) =...
8
votes
6answers
279 views

Calculating remainder of $666^{666}$ when divided by $1000$.

I want to calculate the remainder of $666^{666}$ when divided by $1000$. But for the usual methods I use the divisor is very big. Furthermore $1000$ is not a prime, $666$ is a zero divisor in $\mathbb{...
4
votes
1answer
67 views

For any $n$ positive integers ($n\geq 5$) exactly 3 or 4 of them are equal to each other modulo $2^m$ for some $m$

How can one prove that for any $n$ distinct positive integers, $n\geq 5$, there exists $m$ such that exactly 3 or 4 of them are equal to each other modulo $2^m$? I tried to prove it for small $n$. ...