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
15 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
17 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 ...
129
votes
1answer
7k views

A variation of Fermat's little theorem

Fermat's little theorem states that for $n$ prime, $$ a^n \equiv a \pmod{n}. $$ The values of $n$ for which this holds are the primes and the Carmichael numbers. If we modify the congruence ...
2
votes
0answers
28 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
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 ...
2
votes
1answer
62 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
25 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
37 views

Can this congruence be simplified?

$$p(p+1) \equiv -q(q+1) \bmod pq$$ Can this be reduced to an easier format?
4
votes
3answers
109 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 ...
3
votes
1answer
31 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 ...
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
60 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 ...
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
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
5answers
77 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, ...
-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}= ...
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: ...
1
vote
2answers
86 views

Arithmetic on modular curves

I had tried to read the first few pages of Glenn Stevens' Arithmetic on Modular Curves, but it is somehow extremely unreadable to me, the text format is odd and stating too much facts without ...
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, ...
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 ...
0
votes
1answer
289 views

Calculating nCr mod M using inverse multiplicative factors

The method used for calculating nCr mod M is: fact[n] = n * fact[n-1] % M ifact[n] = modular_inverse(n) * ifact[n-1] % M And then nCr is calculated as ...
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 ...
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.
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 ...
1
vote
2answers
62 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 ...
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 ...
1
vote
3answers
93 views

Does $p \equiv q \pmod a \implies p \bmod a = q \bmod a$?

I'm trying to understand the notation $p \equiv q \pmod a$. Does does it implies that $p \bmod a = q \bmod a$? for example: $$ \begin{align} 5 \bmod 7 &= 5 \\ 12 ...
2
votes
4answers
110 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.
3
votes
4answers
904 views

how do I calculate inverse modulo of a number when the modulus is not prime?

I came through Fermat's Little theorem, and it provides a way to calculate inverse modulo of a number when modulus is a prime. but how do I calculate something like this 37inverse mod 900?
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 ...
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
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$.
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 ...
2
votes
4answers
138 views

The final digit of fourth powers

I am working on "Elementary Number Theory" By Underwood Dudley and this is problem 13 in Section 4. The question is "What can the last digit of a fourth power be?" I got the correct answer but I'm ...
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
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 ...
4
votes
1answer
74 views

An infinite sum based on the mod-parity of Euler's totient function

Let $\bmod( m,k )$ be the remainder when $m$ is divided by $k$: $0,1,\ldots,m{-}1$. Let $\phi(n)$ be Euler's totient function: the number of relatively prime numbers smaller than $n$. So for ...
5
votes
1answer
102 views

Sum of elements of a finite field

Let $F$ be a finite field and $i$ an integer. Calculate the sum of all the elements of $F$, each raised to the $i$th power. My approach so ...
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
4answers
317 views

How to find inverse of 2 modulo 7 by inspection?

This is from Discrete Mathematics and its Applications By inspection, find an inverse of 2 modulo 7 To do this, I first used Euclid's algorithm to make sure that the greatest common divisor ...
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 = ...
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
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 ...