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
12 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 ...
6
votes
1answer
132 views

$1989|n^{n^{n^{n}}} - n^{n^{n}}$ for integer $n \ge 3$

Before anyone comments, yes this is kind of a duplicate of Prove that $1989|n^{n^{n^{n}}} - n^{n^{n}}$ . The problem that I'm having I don't see the $n=5$ as a counterexample. Also if anyone wants to ...
4
votes
0answers
130 views
+50

Test about prime gaps: which conclusions can be drawn from the results?

I did the following test: For every prime, take the prime gap distance $dp$ to the previous prime and the next prime $dn$, then calculate $a=(pp\ mod\ dp)$ and $b=(np\ mod\ dn)$. If $a$ or $b$ ...
4
votes
1answer
181 views

Prove that $1989\mid n^{n^{n^{n}}} - n^{n^{n}}$

Having difficulty in proving this: $1989\mid n^{n^{n^{n}}} - n^{n^{n}}$ for all $n \in \Bbb N$. Prime factorization of $1989$ is $3^2 \times 13 \times 17$. Please Help!
3
votes
0answers
26 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 ...
0
votes
0answers
72 views

Is there a definition about prime pairs $(p,q)$,$\quad q=(n \quad mod \quad p)$ and $2p+q=n (odd)$?

I am studying congruences and I have observed this kind of prime pairs $(p,q)$ related to odd numbers. Here is the definition: $\forall n=1+2k,\quad k\ge5,\quad k \in \mathbb N, \quad \exists$ $p ...
1
vote
0answers
59 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
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
4answers
110 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
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
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
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
38 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: ...
16
votes
2answers
2k views

what is the remainder when $1!+2!+3!+4!+\cdots+45!$ is divided by 47?

Can any one please tell the approach or solve the question what is the remainder when $1!+2!+3!+4!+\cdots+45!$ is divided by $47$? I can solve remainder of $45!$ divided by $47$ using Wilson's ...
1
vote
1answer
42 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
48 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$ ...
0
votes
3answers
48 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 ...
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
5answers
5k views

How often in years do calendars repeat with the same day-date combinations (Julian calendar)?

E.g. I'm using this formulas for calculating day of week (Julian calendar): \begin{align} a & = \left\lfloor\frac{14 - \text{month}}{12}\right\rfloor\\ y & = \text{year} + 4800 - a \\ m & ...
-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$ ...
-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
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
16 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 [on hold]

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?
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?
0
votes
1answer
429 views

What will be the multiplicative inverse of square root of 5 with respect to a natural number $M$?

Can such a number $N$ be found such that $\sqrt{5}N \equiv 1 \mod M$? If no,what can be the best approximation for $N$?
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$ ...
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$?
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 ...
1
vote
3answers
3k views

How can a = x (mod m) have multiple meanings in modular arithmetic?

It seems to me that a = x (mod m) can mean either that a is the remainder of x divided by m or that the remainders of a and x are the same when divided by m (eg. with respect to mod m). For example: ...
12
votes
2answers
133 views

Remainders of Fibonacci numbers

Let $a>b$ be positive integers. Is there a Fibonacci number that is $b$ modulo $a$? We know that the Fibonacci numbers are periodic modulo $a$. Indeed, consider pairs $(F_i,F_{i+1})$ modulo $a$. ...
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 ...
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 ...
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? ...
17
votes
6answers
2k views

Linear diophantine equation $100x - 23y = -19$

I need help with this equation: $$100x - 23y = -19.$$ When I plug this into Wolfram|Alpha, one of the integer solutions is $x = 23n + 12$ where $n$ is a subset of all the integers, but I can't seem ...
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} ...
2
votes
3answers
102 views

what is remainder when $(((3!)^{5!})^{7!})^{9!…}$ is divided by 11

$$(((3!)^{5!})^{7!})^{9!...}$$ when divided by 11 what will be the reminder? Hint is appreciated Sorry I do not know how to start this problem, so I have not shown my efforts!
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, ...
1
vote
2answers
63 views

Modulus and Fermat's Little Theorem

How do I calculate $ 11^{23} \bmod{163} $ using fermat's little theorem ?
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$ ...
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 ...
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.
0
votes
1answer
23 views

If the euclidean algorithm is used to solve an equation ( i.e., $ax = b \mod(z)$) is the solution unique?

I have solved such an equation using the euclidean algorithm. However, unlike other methods, this gives one solution. Is this just one solution or the only solution. Help is much appreciated. Thank ...