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
2answers
26 views

Proof of Little Fermat's Theorem for a=7

In the book I read there are proofs of FLT for certain cases before the common case. When a=7, authors first write that it's possible to check all remainders of $a\mod7$, and then that it's ...
1
vote
0answers
51 views

[ANSWERED]Is $\{n, n^{2} n^{3}\}$ a group under multiplication modulo $m = n + n^{2} + n^{3}$?

My number theory has been lacking, so i decided to practice it a bit. I have gotten better in the sense that i can figure out where to begin approaching a problem, but i am having trouble seeing the ...
1
vote
3answers
39 views

Simplifying a proof by contradiction: if $a\equiv 1\bmod 5$, then $a^2\equiv 1\bmod5$

Prove the following either by Direct Proof or by Contraposition: Suppose $a\in\mathbb{Z}$, if $a\equiv 1\pmod 5$, then $a^2\equiv 1\pmod5$ Suppose $a\equiv 1\pmod 5$ Then $5|\left(a-1\right)$, ...
0
votes
1answer
19 views

Explanation of congruence and modulo

Consider the set $A$ = {${-6, -5 -4,-3,-2,-1,0,1,2,3,4,5,6,7,8,9,10,11,12}$} Write down the numbers in $A$ congruent to $1$ modulo $4$. Can someone explain why the answer is not $-4,-1,-4,8,12$ ...
2
votes
1answer
27 views

The modular n-th root (mod p*q)

I am interested in the solution of the following modular equation. Is the solution unique? If not, how difficult do find more than one solutions? $$x^n \equiv a \; \bmod (p\cdot q)$$ where $p$ and ...
1
vote
1answer
28 views

Why is any number to the 1,5,9,13, etc. modulus 10 itself?

Why is $n^{4k+1} \% 10 = n$ for any integer $n$ and any whole number $k$? What about base 10 math makes this sop?
1
vote
0answers
7 views

If there is a subset with sum divisible by n, then take out an integer of the subset. How many moves?

Fix an integer $n \ge 2$. A finite set $A \subset \mathbb{N} $ is given. Define $ s(X) = \sum_X x $, where $ X $ is a finite set. We know that $n \mid s(A)$. We can do just one move: if there is a ...
0
votes
1answer
18 views

(Statistics)Probability of given sum in dice tossing [on hold]

I need some help with this problem: By tossing two dice, what is the probability of: i) Total sum of 7 ii) Difference of 5 iii) Total sum multiple of 7 Thanks everyone ~Chris
1
vote
2answers
58 views

Find the remainder when $2^{561}$ is divided by $561$ using simple congruence properties.

$2^{561}\equiv ? \pmod{561}$ Few observations : $561 = 3\times 11\times 17$ So Fermat's little theorem is not useful here. Any hints ? If possible, kindly avoid carmichael numbers/group theory/euler ...
0
votes
3answers
43 views

Congruences in number theory

I am working on a worksheet on number theory and I have to solve the following congruences: $$7^{128}=n\mod 13$$ Find $n$. And $$28x^2=1\mod37$$ How should I solve these congruences? I have no clue ...
0
votes
1answer
44 views

Exist an explicit formula to calculate the minimum number of divisions by two that leave a rest < 0.5?

I have a number $x \in \Bbb R/\Bbb Z$ (i.e. any number but entires) and I want to know if exist a explicit formula that evade recursion to calculate the minimum n that $$\frac{x}{2^n}\mod ...
0
votes
0answers
21 views

Modular nth roots, e.g. $x^5 \equiv 6 \pmod{31}$

I want to algorithmically solve the (large integer) modular root equation $$x^n \equiv a \pmod {p^k},$$ assuming for simplicity that $p$ is prime, $\gcd(a,p)=1\;$ and $n$ odd. If $q \equiv n^{-1} ...
3
votes
1answer
166 views

How to compute this sum?

I want to sum the following: $$f(n) = \sum_{i=1}^n (i^3 \cdot (n \mod i))$$ Since the sum can be huge I have to output the sum modulo some given number m. How can I approach this problem? Also, n ...
0
votes
4answers
1k 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 & ...
0
votes
0answers
21 views

CRT Algorithm using InvMod + Undefined

I am trying to implement a modified CRT function in c++ that calls a function called invMod which is simply the inverse modulus function. I am having difficulty randomly generating values while ...
0
votes
1answer
286 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$?
1
vote
1answer
12 views

$A^{-1}x \pmod{26}$ and coprime requirement in Hill cipher

I am reading Hill cipher from wiki page and I have been stuck on this thought for a while. Why is there a requirement for $\det(A)$ and $26$ to be coprime in Hill cipher ? Anybody familiar with Hill ...
3
votes
1answer
74 views

Find all $x,y\in\mathbb{Z}$ s.t $2x^3-7y^3=3$

Find all $$x,y\in\mathbb{Z}$$ such that $$2x^3-7y^3=3$$ Solution: We consider first $$2x^3-7y^3\equiv3 \pmod 2$$ $$5y^3\equiv 1 \pmod 2$$ $$y^3\equiv 1 \pmod2$$ which has solution $y\equiv 1 ...
1
vote
1answer
41 views

Calculation of products of powers using Modular Exponentiation

I need to devise an algorithm that outputs $x^a * y^b$ (mod $m$) on an input of $m, x, y, a, b$ using the binary left to right modular exponentiation algorithm. It should be able to compute $x^{22} * ...
1
vote
0answers
111 views

Is this function $f^n_b : \mathbb{R}_{\geq 0} \to \mathbb{R}_{\geq 0}^n$ a surjection?

In this text the fractional part of a real $x$ shall be denoted $\{x\}$, such that $x = \lfloor x \rfloor + \{x\}$. Let the set of functions $f^n_b : \mathbb{R}_{\geq 0} \to \mathbb{R}_{\geq 0}^n$ be ...
0
votes
2answers
22 views

Proof of $g^a \equiv 1 \pmod{m}$ and $g^b \equiv 1 \pmod{m} \quad \implies \quad g^{\gcd(a,b)} \equiv 1 \pmod{m}$

I am trying to understand the following: $$g^a \equiv 1 \pmod m \quad \text{and} \quad g^b \equiv 1 \pmod{m} \quad \implies \quad g^{\gcd(a,b)} \equiv 1 \pmod{m}.$$ I have tried a few approaches, ...
0
votes
0answers
29 views

How can I solve equations involving modulo both side like this one?

I need to find $x \bmod m$ from the below equation: $$((p \bmod m)(x \bmod m)) \bmod m \equiv q\bmod m$$
1
vote
2answers
574 views

Doing modular division when denominator and modulus not coprime

So normally if you calculate $n/d \mod m$, you make sure $d$ and $m$ are coprime and then do $n[d]^{-1}\mod m$ , all $\mod m$. But what if $d$ and $m$ are not coprime? What do you do?
-4
votes
1answer
68 views

Series of $i^3 $* ( N mod i) [closed]

I need to get a simplified form of the following series, I don't want to calculate each term of the series (as it would be inefficient w.r.t time). I want to get it simplified may be in some sort of ...
0
votes
5answers
52 views

How to work out $-1 \bmod 7$?

What is the working out for $-1 \bmod 7$? I can do it if the numbers are positive just the negative throws me off.
-3
votes
3answers
182 views

Congruence $x^n\equiv2 \pmod{13}$ (Multiple Choice)

I was trying to solve the following problem.Please help. Consider the $x^n\equiv2 \pmod{13}$. It has a solution for $x$ if $n=5$ $n=6$ $n=7$ $n=8$ It may have more than one correct options. Thnx ...
0
votes
1answer
19 views

On the Product of Congruence Classes over $\mathbb{Z}$

Is it possible to multiply an element $a$ of $\mathbb{Z}_4$ to an element $b$ of $\mathbb{Z}_2$? If so, what are the needed conditions? To which set ($\mathbb{Z}_4$ and $\mathbb{Z}_2$) does $a\cdot b$ ...
1
vote
1answer
38 views

How to figure out congruences involving large numbers?

The one I'm stuck on now is: $$3^{1996001} ≡ 2664001 \mod 3992003$$ Absolutely no idea how to get this! I could whittle it down if I knew the multiplicative order of $3$ modulo $3992003$, but I have ...
-1
votes
0answers
25 views

How to find correct value of (a%M/b)? where M is modulo operator

I want to find a/b . but since a is very large i am taking modulo of it. and now when i divide it by b then it gives wrong answer. So I want a/b from a%m/b. Please tell me how to I get that. here a ...
2
votes
1answer
577 views

Solving Diffie–Hellman problem for low primitive root

What's a good way of solving the Diffie–Hellman problem when those exchanging the message have chosen a low primitive root $g$ (e.g. $g=3$)? Of course you could brute force it but I'm interested in ...
1
vote
3answers
71 views

Remainder of dividing $x^{137}+x+1$ by $x+5$

In $\mathbb{Z}_7[x]$, what is the remainder of dividing $x^{137}+x+1$ by $x+5$? I can not find how to solve this problem of modular arithmetic. Anybody could tell me only as I proceed to solve this ...
0
votes
0answers
22 views

In $\mathbb{Z}(430)$, What is the value of $x ?. 9 * x = 80 ^{ -1}$

In $\mathbb{Z}(430)$, What is the value of $x ?. 9 * x = 80 ^{ -1}$ I can not solve this problem. I the inverse of a number is calculated in my case is 80 But in this case the number is multiplied ...
0
votes
1answer
53 views

Closed form of the series

I want to evaluate $\sum_{i=1}^{n} (x+i)^4$ So what i did is, after expanding it i reduce it to following form $ x^{4} * n + 4 x^{3} * \sum_{i=1}^{n}i + 6x^2\sum_{i=1}^{n}i^{2} + ...
4
votes
2answers
127 views

Solving strange Modular arithmetic

I'm trying to solve a form of modular arithmetic I've never seen before. I'm completely stuck. Any hints in how to crack this would be of great help. $$ -18 \equiv 19y \pmod{1967-y}$$ Or ...
2
votes
0answers
28 views

Fast algorithm/formula for serial range of modulo of co-prime numbers [migrated]

In my project, one part of problem is there. But to simplify, here the problem is being formulated. There are two positive co-prime integers: $a$ and $b$, where $a < b$. Multiples of $a$ from 1 ...
0
votes
0answers
17 views

how to use inverse moldulus operation while taking modulus?

i want to calculate (a/b)mod m which is definitely not equal to (a%m)/(b%m)..... so we can calculate the inverse of b and multiply it to a then take modulus i.e (a%m * x%m)%m where (b*x=1 mod m) and ...
2
votes
1answer
53 views

How can I compute the following fast?

What approach should I adopt for computing the following problem fast? $$f(n) = \sum_{i=1}^n (n \mod i)$$ $$ 1\le n \le 10^{10}$$ Since the answer can be huge I have to output it modulo some given ...
0
votes
1answer
53 views

Variation of Fermat's Theorem

I'm am having trouble coming up with a proof strategy for the following variation of Fermat's Theorem. If the solution is trivial, please forgive me, this is my first encounter with this theorem. I ...
1
vote
0answers
32 views

Rational equality modulo $p$

Assume that we have two rational expressions $f,g\in \mathbb{Z}(x,y_1,\ldots,y_n)$ with the property that the variable $x$ can only appear in the numerator of $f$ while only in the denominator of $g$. ...
3
votes
1answer
35 views

Find the order of $2$ in $\mod 2^{n} -1 $

Find the order of $2$ in $\mod 2^n-1$ I know that the order of $2$ in $\mod 2^n-1$ is the smallest positive integer $k$ such that $$2^k \equiv 1 \pmod {2^n-1}$$ How to proceed from here ? Any ...
0
votes
1answer
23 views

$(x \equiv k^2 \mod 3) \iff x \equiv 1 \mod 3 $

Is it true that if 3 does not divide $x$, $$x\equiv k^2\mod 3 \iff x\equiv 1 \mod 3$$ If the above statement is correct , There are two parts to prove $$x\equiv k^2\mod 3 \implies x\not\equiv 0 ...
1
vote
4answers
80 views

Calculate $85^{2014}\bmod {82}$ [closed]

Calculate the following equation $$85^{2014}\equiv x \bmod {82}$$ Answer is 73 in Wolphram Alpha, but I always lose myself doing the step by step
0
votes
0answers
19 views

Simple problem to find value of expression mod m?

Find value of expression mod M? Expression is $$\frac { 1 }{ 30 }(-6 x ^ 5 + 15 x^4 - 10x^3 + x+ 6y^5 + 15 y^4 + 10 y^3 - y) $$ 1 <= M <= 100000 where x and y are given integers <= 10 ^ 10 ...
2
votes
0answers
33 views

Is there a cycle for modulo operation on a floor?

I have a floor $${\left\lfloor\frac{n}{i}\right\rfloor},$$ where i varies from 1 to n (n can be upto $10^{10}$), and there's another number given 'm' (m upto $10^{5}$). Does ...
0
votes
2answers
75 views

how can i find modulus of the sum of first n natural numbers raised to power 4? [closed]

suppose i am given with a number p and a number n then i want to calculate : (1^4 + 2^4 + 3^4 + 5^4 +........n^4)%p earlier i was trying to use the standard formulae of sum of first n natural ...
2
votes
1answer
133 views

How is this done?

The question here: A number when successively divided by 9, 11 and 13 ... I found the answer to it in a book and this was the answer: ...
2
votes
0answers
47 views

Closed form for the sum $\sum_{a=1}^{b} a^3\cdot (b \bmod a)$

How can we simplify $\sum_{a=1}^{b} a^3\cdot (b \mod a)$? For $a \ge \frac{b+1}{2} $ to $a = b$ it reduces to $$\sum_{a\ge \frac{b+1}{2}}^{b}a^3\cdot (b-a)=b\cdot\sum_{a\ge ...
0
votes
0answers
21 views

To compute (a/b)%c when b and c are not coprime to each other

how to compute (a/b)%c when b and c are not coprime to each other? here (a%b)=0.I know that when gcd(b,c)=1 it can be easily obtained by euclidean algorithm.But how do you solve the equation when ...
-2
votes
2answers
136 views

How to find sum of 4th power of n numbers mod m [closed]

How can i calculate $1^{4} + 2^{4} + 3^{4} + 4^{4} .....+n^{4} \pmod m$ where $1 \le m \le 10^5$ and $1\le n \le 10^{20}$. I can't use the formula here because it will Overflow the limit of long long ...
1
vote
2answers
42 views

Modulus of Fraction

I just want to confirm I am doing this problem correctly. The problem asks to compute without a calculator: 3 * 2/5 mod 7 The way I am solving the problem: 3 * 2/5 mod 7 3 * 2 * 1/5 mod 7 gcd(5,7) ...