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
3answers
53 views

Cyclic groups and Unit groups

So I wanted to find the the subgroup $3 \in U(20)$ where $U(20)$ is the unit group of $\mathbb Z_{20}$ (i.e. all integers in $\mathbb Z_{20}$ that are relatively prime to $20$). I thought that this is ...
0
votes
1answer
43 views

Remainder of $7^{220}$ when divided by $8$

How can I find out what is the remainder when I divide $7^{220}$ by $8$ using modular arithmetic and without using any theorems such as Fermat's Little Theorem or Chinese Remainder Theorem?
2
votes
1answer
35 views

A modular identity

Is it true that $p \equiv 1 (\mod{6}) \iff p \equiv 1 (\mod{12}) \vee p \equiv -5 (\mod{12})$. It's obvious that $p \equiv 1 (\mod{12}) \vee p \equiv -5 (\mod{12}) \implies p \equiv 1 (\mod{6})$. ...
1
vote
1answer
25 views

Modular arithmetic with different moduli?

I am stuck on a problem involving numbers being reduced by two different moduli. Assume I have the following two numbers $g_1$ and $g_2$: $g_1 = (2^{1024} \mod(p)) \mod(q)\\ g_2 = (2^{1234} \mod(p)) \...
1
vote
6answers
63 views

What is $5^{-1}$ in $\mathbb Z_{11}$?

I am trying to understand what this question is asking and how to solve it. I spent some time looking around the net and it seems like there are many different ways to solve this, but I'm still left ...
0
votes
3answers
27 views

Why for $ax \equiv b\pmod{n}$ to have solutions it's necessary that $gcd(a, n) | b$?

When finding the solutions of $$ax \equiv b\pmod{n}$$ I've been given an algorithm which starts by testing that the $\text{gcd}(a, n)|b$. How can I show (for understanding better the topic) that if $...
1
vote
0answers
26 views

Proof that coprime cubes are divisible by $n$

I would like to ask if my proof is correct. Task is to prove that $$ n \big| \left( \sum_{0 < a < n \atop (n, a) = 1} a^3 \right), $$ where $n>2$. My proof: Take a number $k$ coprime to $n$...
3
votes
1answer
108 views

Do circular tapes exist in Turing Machines?

I've been looking for information about this topic without success. Have someone described Turing Machines over circular tapes instead lineal and infinite? Like the tape could be described with ...
0
votes
1answer
27 views

Modular invertibility of a primitive matrix

Question. If a matrix $A$ has a primitive characteristic polynomial modulo $p$, how to prove it is invertable modulo $p$. Due to my prior question I know that if a matrix is invertable modulo a ...
1
vote
1answer
47 views

computing modulo with large numbers

I want to compute $$36^{293}\equiv \alpha \quad \text{mod}\, 1225284684$$ with a pocket calculator, but I'm not sure how to do this, because the modulus is so large. Is there a way to do this?
0
votes
0answers
55 views

Solving Simultaneous Modulus Equations

I'm trying to figure out how to solve multiple simultaneous modulus equations. The problem I'm hitting is that I get to a point where there's too many unknowns or degrees of freedom for how many ...
2
votes
1answer
26 views

Modular invertibility of a matrix

Consider $\mathbf{B}$ be a matrix invertable modulo a prime number $p$. Is it always possible to say that $\mathbf{B}$ is always invertable modulo $p^\alpha,\, \alpha \in \mathbb{N}$. It seems that ...
0
votes
1answer
31 views

Please check linear congruence equation solution

Preface At first I wanted to ask the community to solve the equation for me as I knew very little about modular arithmetic. But then I decided to try and found that this is a linear congruence ...
1
vote
1answer
94 views

Solving a system of inequalities in modulo N

I have a problem that boils down to two unknowns, $X_1$ and $X_2$, where: $X_1 \cdot M + A\bmod N = X_2$ And: $X_1 \lt L_1\bmod N$ $X_2 \lt L_2\bmod N$ I can try every possible $X_1 \lt L_1$ ...
0
votes
1answer
23 views

Count of solutions to matrix equations

Given these modular equations: $$a_{1,1} x_1 + a_{1,2} x_2 + \cdots + a_{1,n} x_n = b_1 \bmod p $$ $$a_{2,1} x_1 + a_{2,2} x_2 + \cdots + a_{2,n} x_n = b_2 \bmod p $$ $$\vdots$$ $$a_{m,1} x_1 + a_{m,...
0
votes
4answers
70 views

Prove or disprove: For all positive integers n and for all integers a and b, if a ≡ b mod n, then a^2 ≡ b^2 mod n.

Prove or disprove: For all positive integers $n$ and for all integers $a$ and $b$, if $a \equiv b \mod n$, then $a^2 \equiv b^2 \mod n$. Prove or disprove: For all positive integers $n$ and for all ...
2
votes
4answers
82 views

Find last two digit

I have the following task: $1997^{1998} \pmod {100} = ?$ How to find it? Could you please, explain to me step by step with? Can you suggest any solution, without using Euler function? But rather, ...
1
vote
1answer
76 views

Integers with cubes ending $\ldots888$. [duplicate]

This is a coding question.Here we have to find the $k$-th value in which we get $888$ as the last three numbers for a cube of a number. For example, if $k=1$ the first value with last three numbers as ...
1
vote
1answer
46 views

Inverse modular arithmetic method

We have that if $nd\equiv k \mod p$, then $\dfrac{k}{n}\equiv d \mod p$. This is useful to solve small versions of CRT, for example: $$2\cdot 7\equiv3\mod11$$ so $$\dfrac{3}{7}\equiv 2\mod11$$. It ...
1
vote
2answers
106 views

Modular Arithmetic and prime numbers

With respect to the maths behind the Diffie Hellman Key exchange algorithm. Why does: (ga mod p)b mod p = gab mod p It might be fairly obvious, but what basic maths guarantees this? Why does the ...
3
votes
0answers
102 views

Lehmer's totient problem generalization (adding a constant )

Lehmer's totient problem is an well-known open problem which states that the divisibility : $$\phi(n) \mid n-1$$ holds only for primes . This motivated me to ask the following : For which ...
1
vote
1answer
67 views

a mod -b (Maple disagrees with Wolfram)

According to my professor (and maple) a mod -b such as 1000%(-9) Is an invalid question that cannot be answered, since c>0, he claimed also that Maple will respond with "Error, invalid mod". ...
0
votes
1answer
64 views

Is this a good generating function for Sum-of-divisors function?

I have an expression for the sum-of-divisors function defined as $$\sigma(n)=\sum_{d\mid n}d.$$ However I do not know how nontrivial or practical it actually is. Let us define $$A=\frac{b}{2}-\frac{b}...
1
vote
2answers
54 views

Why distribution of multiple recursive random number generators is uniform?

I was reading the article of L'Ecuyer on random number generation. The title of this article is "Uniform Random Number Generation". One of the proposed PRNGs there, is multiple recursive random ...
2
votes
2answers
84 views

Prove that $\sum_{t=1}^{p-1} \frac{t^2-1}{t^2+1} \equiv 0 \pmod p$

I'm trying to prove the statement $\sum_{t=1}^{p-1} \frac{t^2-1}{t^2+1} \equiv 0 \mod p$ and I don't really know where to start. Obviously $\sum_{t=1}^{p-1} \frac{t^2-1}{t^2+1} = 2\sum_{t=1}^{(p-1)/2} ...
3
votes
0answers
47 views

Is this expression for $x\pmod n$ interesting; nontrivial?

For example, we would get several interesting results if we had a formula for $x\pmod n$ that was uniformly convergent, however, according to Wikipedia (Floor and Ceiling Functions) these formulas do ...
0
votes
1answer
69 views

Modulus with negative remainder

It has previously been asked about -a mod b, and, summarizing my gain: -1000 % 9 -1000/9 = -111.111.... 9*112-1000 = 8 This is the method I've found to be effective. 1. What is the easiest ...
5
votes
2answers
73 views

Does every prime of the form $4k+1$ divide a number of the form $4^n+1$?

While playing around with Fermat's little theorem I was asking myself the question in the title and I can't answer it...
0
votes
1answer
39 views

Security of such cryptosystem design?

Is one able to reveal $m$ when $$С = (m + r)^e \bmod N$$ $C$ is known $r$ is known $e$ is known $N$ is known and not prime
1
vote
4answers
41 views

Simulataneous equations

Suppose you have the following system of linear congruence $2x+5y$ is congruent to 1 (mod6) $x+y$ is congruent to 5 (mod6) where $x,y \in \mathbb{Z}$ How would you obtain a general solution for ...
1
vote
1answer
38 views

Proving a simple modulo equality

I'm probably lacking some basic concept here but I'm trying to prove that $$ ((a \mod k) \cdot k + b) \mod k = (a \cdot k + b) \mod k$$ I get stuck at the passage where, applying distributive ...
2
votes
0answers
40 views

$a$ and $n$ are relatively prime then there exists an integer $k$ such that $ak \equiv 1(\mod n) $.

Let $n \in Z$, $n > 1$ and let $a \in Z$ with $1 \leq a \leq n$. Prove that if $a$ and $n$ are relatively prime then there exists an integer $k$ such that $ak \equiv 1(\mod n) $. Proof: Suppose $(...
2
votes
1answer
115 views

Difficult sets of Equations, counting

Let $ m$ be the number of solutions in positive integers to the equation $ 4x+3y+2z=2009$, and let $ n$ be the number of solutions in positive integers to the equation $ 4x+3y+2z=2000$. Find the ...
2
votes
2answers
74 views

Can this congruence be simplified?

$$p(p+1) \equiv -q(q+1) \bmod pq$$ Can this be reduced to an easier format?
3
votes
1answer
42 views

If $b \equiv 0 \pmod a$ and $c \equiv 0 \pmod b$, then $c \equiv 0 \pmod a$

The question is If $b \equiv 0 \pmod a$ and $c \equiv 0 \pmod b$, then $c \equiv 0 \pmod a$. My attempt is that $b \equiv 0 \pmod a$ can be written $a\mid b-0 = a\mid b$ and the same with $c \equiv 0 ...
2
votes
1answer
16 views

solving $\left( m'\right) ^{d}\equiv m\cdot m^{r\left( p-1\right) \left( q-1\right) }\left( mod\ p\right) $

maybe someone can help: I am trying to follow a lecture and there is: given : $\left( m'\right) ^{d}\equiv m\cdot m^{r\left( p-1\right) \left( q-1\right) }\left( mod\ p\right) $ and : $ m^{p-1} \...
0
votes
4answers
97 views

Solve the congruence $31x\equiv 5 \pmod{23}$

I've used the Euclidean Algorithm to solve congruences of the form $$ax \equiv b \pmod n$$ where $n >a$, for example: $16x \equiv 5 \pmod{29}$. When $n <a$, for example, $$31x \equiv 5 \pmod{23}$...
1
vote
1answer
36 views

Solutions to a quadratic diophantine modular equation

I wonder if solutions are known for this quadratic diophantine modular equation: x²=y² mod (p1 p2) where p1,p2 are given primes and x,y are integers and unknowns?
4
votes
0answers
135 views

Connections between Fibonacci and natural numbers

Here are some known facts about the Fibonacci numbers and then some questions regarding them . 1.Carmichael's theorem : For every $n>12$ $F_n$ has a prime divisor which doesn't divide any of ...
-1
votes
2answers
32 views

Modulo question: $(\operatorname{rand}[0,n-1]+\operatorname{rand}[0,n-1]+\cdots+) \pmod n$?

I have a problem: There are $i$ betters, each choose a random value between [$0$ and $n-1$] Then we add all the $i$ numbers and we do (mod $n$) $$\text{Final number}= (\operatorname{rand}[0,n-1]+\...
0
votes
2answers
96 views

All squares above 6 have an even number of multiples of 10. Why?

I was recently looking at a puzzle in Martin Gardner's book: Two brothers sell their heard of sheep, and receive the same number of dollars per sheep, as there were sheep in the heard. They ...
1
vote
1answer
39 views

Find the maximum value of the quotient

Given a real number $x,$ let $\lfloor x \rfloor$ denote the greatest integer less than or equal to $x.$ For a certain integer $k,$ there are exactly $70$ positive integers $n_{1}, n_{2}, \ldots, n_{70}...
2
votes
1answer
60 views

Sum of digits modulo a polynomial

I made the following problems a while ago but I can't solve them (though I don't think it's too hard) 1.Let $s(n)$ be the digits sum of $n$. Let also $f(n)$, $g(n)$ $\in Z[X]$ . Assume that: $$...
3
votes
1answer
35 views

Simple congruence relation (modular arithmetic)

Let $p \neq 2,5$ be prime. Suppose you know that $p \equiv 1 \mod 4$ and that $(\frac{p}{5}) = 1$, with $(\cdot)$ the Legendre Symbol. How does it follow that $p \equiv 1 \mod 20 $ or that $p \equiv ...
1
vote
1answer
27 views

Modular arithmetics: one sequence is equal to another read backwards

I was doing some music theoryzing (circles of fifths and fourths) and found an interesting problem. Suppose, we have $2$ sequences: A and B. A $a(i+1) = a(i) + 7 \pmod {12}$ $a(0) = 0$ As $7$ and ...
2
votes
1answer
58 views

How to eliminate the leading coefficient in this congruence?

$$ax^2 = b \bmod m$$ I am trying to get rid of the $a$ so I can apply Tonelli-Shanks to the result to solve for $x$. But since $a$ and $m$ are not always coprime, I cannot always multiply both sides ...
0
votes
2answers
41 views

Is it possible to simplify $a = b\mod(mn)$

I don't think so but can anyone verify that there is no way to technically rearrange this equation so that there is no $\mod(xy)$? I'd like to part the x and y somehow.
1
vote
1answer
43 views

How do I get rid of the coefficient in this congruence?

$$ax^2 = b \bmod m$$ I am trying to get rid of the $a$ so I can apply Tonelli-Shanks to the result to solve for $x$. But since $a$ and $m$ are not always coprime, I cannot always multiply both sides ...
4
votes
3answers
146 views

Iterated square roots over finite field. When do we hit a nonresidue?

Suppose that we are working within the integers modulo $p$ where $p$ is some odd prime number. Suppose that $x_0$ is a (nonzero) quadratic residue mod $p$ then there exists some $x_1$ such that $x_1^2 ...
1
vote
2answers
175 views

$2017^{2016^{2015}} \mod 1000$

I'm trying to solve the following exercise: $$2017^{2016^{2015}} \mod 1000,$$ here's what I've already come up with: Using Euler's conrgruence, one finds that $$2017^{2016^{2015}} \equiv 2017^{2016^{...