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

1
vote
0answers
5 views

Solving a modulo 3 matrix system, with a constraint on the domain of the solution

Someone on cs.stackexchange suggested to post the mathematical part here, I hope I'm not crossposting. All calculations below are integer calculations under modulo 3. I am trying to solve an integer ...
1
vote
1answer
40 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 ...
0
votes
0answers
17 views

Issue with modular arithmetic problem

So I have a problem with this question I was doing. I found that $94^6+32\cdot28^6$ is divisible by 2013, using a calculator. Since 61 divides 2013, 61 also divides $94^6+32\cdot28^6$. However, i ...
2
votes
2answers
33 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
27 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
14 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
3answers
48 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 ...
0
votes
1answer
22 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?
3
votes
0answers
56 views

Connections between Fibonacci and natural numbers

Here are some known facts about 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 the ...
-1
votes
2answers
27 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}= ...
0
votes
2answers
90 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
28 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, ...
2
votes
1answer
44 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
25 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
21 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
31 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
30 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
31 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 ...
0
votes
0answers
23 views

Equation in one variable in finite ring $\mathbb{Z}/ m\mathbb{Z}$

Let $m = pq$, with $p \neq q$, uneven primes. Suppose you have an equation $f(x) = 0$, with $f(x) \in \mathbb{Z}[x]$, and that you want to know the roots of $f(x)$ in $\mathbb{Z}/m\mathbb{Z}$. Then ...
4
votes
3answers
107 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
60 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 ...
2
votes
1answer
30 views

Is there a proven formula for Pisano periods (Fibonacci numbers taken modulo $n$)?

I've seen on wikipedia this formula: $$\pi_k(p^n) = p^{n-1}\pi_k(p) $$ It says that the formula holds unless p is k-Wall-Sun-Sun prime, or k-Fibonacci-Wieferich prime, that is, $p^2$ divides ...
1
vote
5answers
75 views

Is there a method to calculate large number modulo?

Is there a (number theoretic or algebraic) trick to find a large nunber modulo some number? Say I have the number $123456789123$ and I want to find its value modulo some other number, say, ...
0
votes
1answer
27 views

Weighted sum of angles modulo $\pi/2$

Angle modulo $\pi /2$ means: $(a+ \pi /2) \mathbin{\%} \pi/2=a$, $a \in [0, \pi/2)$, which could be illustrated as a ‘modulo circle’ in the following figure. How to calculate the weighted sum of a ...
6
votes
1answer
62 views

Tzaloa 2015 game problem (piles with $1,2,4 \dots 2^{19}$ coins each)

We have $20$ piles with $1,2,4,8\dots 2^{19}$ coins repectively and two players. In each turn a player must select five piles that have at least one coin and remove exactly one coin from each. Player ...
-5
votes
1answer
31 views

Find the arithmetic progression [closed]

In an arithmetic progression of 40 terms in which the last term is 100 and the common difference is 3, what are the first 39 terms in the progression.
2
votes
4answers
107 views

Last two digits of $3^{7^{2016}}$

I need help with solving this Algebra problem: Find the last two digits of $3^{7^{2016}}$. Preferably using Euler's theorem.
-1
votes
1answer
22 views

Modular Arithmetic Divisibility

Prove that for all integers $n$, exactly one of $n$, $2n − 1$ and $2n + 1$ is divisible by $3$.
0
votes
1answer
18 views

Modular arithmetic proof without using induction

Need some help guys I'm really unsure how to do this, can someone give me a step by step guide please? Show that $10 \mid (3^{4n} + 50n^6 − 11)$ for all $n \in \mathbb{Z}^+$ without using induction. ...
-4
votes
0answers
29 views

find the answer [closed]

Let F(n) be the sum of the minimum number of floor rewirings needed over all possible power-flow arrangements in a hotel of n floors. For example, F(3) = 6, F(8) = 16276736, and F(100) mod 135707531 = ...
1
vote
2answers
19 views

Multiple choice: $S = {x | 0 ≤ x < 280 ∧ x ≡ 3 (mod 7) ∧ x ≡ 4 (mod 8)}$

The question is: Consider the following set of integers: $$ S = \left\{x \left| 0 \le x < 280 ∧ x \equiv 3 \mod 7 ∧ x \equiv 4 \mod 8 \right. ...
1
vote
0answers
61 views

Find the smallest number which leaves remainder 1, 2 and 3 when divided by 11, 51 and 91

While my preparation for exams, came across this question. "Find the smallest number which leaves remainder 1,2 and 3 when divided by 11,51 and 91" Find considerable time in solving this. I have ...
0
votes
2answers
45 views

Modular of big numbers

I have this question which I have trouble comprehending. I am asked to find $$111 + 11113 + 1111115 \mod{11}.$$ Apparently, according the results the answer is 8. But I just can't see how. I have ...
0
votes
0answers
23 views

How to find the greatest remainder of a number that is a multiple of another number

The greatest possible remainder for a multiple of 4 being divided by 6, happens when 4 is divided by 6. I don't understand why the above statement must be true. Is it relying on a well-known ...
0
votes
0answers
27 views

How to get mod value from variable and result

variable v = 256478 mod m = 568742 result r = 256478 v (mod) m = r , 256478 (mod) 568742 = 256478 my question how to find mod (m = ?) value from variable and result (some case my program) v ...
3
votes
1answer
48 views

Unfamiliar Property of Modular Arithmetic

I saw this property listed in Princeton Review's Math GRE book: "For any positive integer $c$, the statement $a\equiv b\mod n$ is equivalent to the congruences $a\equiv b,b+n,b+2n,\ldots,b+(c-1)n\mod ...
0
votes
1answer
31 views

Modular Sequence

Define a sequence $a_n$ as follows: for each positive integer $n$, set $a_n$ equal to the remainder of $n^n$ when it is divided by 101. What is the smallest positive integer $d$ such that $a_n = ...
1
vote
0answers
24 views

Chaining integer division operations

In an assembler program I am writing, I need to (quickly) calculate $a\text{ mod }n$. Now, in the language I am using there is a division instruction that takes two numbers $x$ and $y$ and returns ...
4
votes
1answer
86 views

Infinite exponentiation $n^{n^{n^{…^n}}} \equiv m \pmod q$ , find m?

let $(n,q) \in \mathbb N^{*^2}$ I was wondering if it was possible to find a function $f_q$ such that : $f_q(n)=m$ where $m$ is such that $n^{n^{...^n}} \equiv m \mod q$ or at least an easy way to ...
1
vote
0answers
28 views

Generalized modulo arithmetic

This question (and especially this answer and the comments on it) actually made me think about a sort of generalized modulo arithmetic that would deal with all modulos at once and would basically make ...
3
votes
1answer
37 views

$\binom{n}{k}$ modulo prime power for large $n$ and small $k$

I have to compute several value of $\binom{n}{k}$ mod $p^a$ for prime $p$ over a range of $k$, where $n$ is large and fixed, and $k$ is small and dynamic. Is there a way to speed the process up? If I ...
0
votes
1answer
13 views

Understanding Multiplicative Inverse in RSA

Okay so I am reading up on RSA, trying to understand how it works, and I come across this $ x∈ℤp, x−1 ∈ℤp ⟺ \gcd(x,p) = 1$ Now it then gives an example, as follows: Lets work in the set $ℤ9$, ...
-1
votes
1answer
19 views

If y=4 and z=10, then what are the set of integers modulo z? [closed]

let's consider x = k.z +y then how can we define the set of integers modulo z? and what does set of integers modulo z mean? I am a programmer and I try to understand these things so could any body ...
5
votes
4answers
158 views

“multiplicative inverse in the modulo of the larger number” what does that mean?

while I was reading this artical I have read the following paragraph: The interesting thing is that if two numbers have a $\gcd$ of $1$, then the smaller of the two numbers has a multiplicative ...
20
votes
13answers
2k views

Why do we use “congruent to” instead of equal to?

I'm more familiar with the notation $a \equiv b \pmod c$, but I think this is equivalent to $a \bmod c = b \bmod c $, which makes it clear that we should put a $=$ instead of $\equiv$. What's the ...
-1
votes
4answers
32 views

What is a modular inverse?????

I realize that this question has been asked before; please just bear with me. I looked across the Internet on here, Khan Academy, and many other sites in order to understand what an inverse mod is and ...
2
votes
4answers
51 views

Modular maths: How do I find the remainder?

How do I find the remainder of $5^{22} \pmod{25}$? And also how do I find the remainder of $3^{16} + 7 \pmod{5}$?
0
votes
1answer
84 views

$x^2 + 6y^2 = 2807$ no integer solution

Prove that equation $x^2 + 6y^2 = 2807$ doesn't have solution in the set of integers. Obviously $x^2$ is odd, so $x$ is odd. Then, I taught that every perfect square has the rest $1$ or $3\bmod ...
0
votes
1answer
32 views

Modulo of squared number

I have tested a lot of combinations with integer numbers and it seems like we can say that $y^2 \bmod n$ equals $((y \bmod n)^2) \bmod n$. I can't find any resource that acknowledges this. Is my ...
0
votes
0answers
42 views

$x^2 + y^2 + z^2 = 2007^{2011}$ with $x$, $y$ and $z$ integers [duplicate]

Solve the equations $x^2 + y^2 + z^2 = 2007^{2011}$ in the set of integers.