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
1answer
34 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 ...
0
votes
0answers
15 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
1answer
51 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} ...
2
votes
0answers
40 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 ...
1
vote
1answer
22 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 ...
6
votes
2answers
65 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...
1
vote
1answer
30 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
0
votes
2answers
20 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 belong to the set of Integers How would you obtain a general ...
1
vote
1answer
22 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
31 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 ...
1
vote
0answers
7 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 ...
2
votes
1answer
95 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
26 views

Issue with modular arithmetic problem [on hold]

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
39 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
37 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
49 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
24 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
62 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
28 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
91 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
29 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
45 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
26 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
32 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
32 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
110 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
63 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
78 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
63 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 ...
2
votes
4answers
113 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. ...
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
62 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 ...