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

Modulus of large powers

Given an array of N integers where $2 ≤ N ≤ 2×10^5$ and each element in array is less than $10^{16}$. Now I am given a variable $X$ that can also go up to $10^{16}$. We need to find if $X \mid ...
0
votes
2answers
84 views

Find all non-trivial triplets $(a,b,c)$ such that $ a+b^{d}\equiv0\pmod c $ for all $d>0$

Let $a,b,c$ be co-prime integers $>2$ . Find all non-trivial triplets $(a,b,c)$ such that $ a+b^{d}\equiv0\pmod c $ for all $d>0$.
-2
votes
1answer
286 views

Modulo of a large sequence of $1$s

Given two numbers $N$ and $M$, we need to find the remainder when $111 \cdots1$ ($N$ times) is divided by $M$. Here $N$ can go up to $10^{16}$ and $M$ up to $10^9$. How to solve this problem? ...
0
votes
1answer
76 views

Use the extended euclidean algortithm to solve this inverse?

Having trouble with understanding this. $$d \equiv 7^{-1} \pmod {360}$$ So far i have got $$360 = 7 \cdot 51 + 3$$ $$7 = 3 \cdot 2 + 1$$ $$3 = 3 \cdot 1 + 0$$ Now i am stuck on the next step ...
7
votes
0answers
346 views

Decoding Gauss' Easter Algorithm

In 1800, Gauss published this algorithm for computing the date of Easter in a given year $year$: $a = year \mod 19$ $b = year \mod 4$ $c = year \mod 7$ $k = \lfloor year/100 \rfloor$ $p ...
1
vote
1answer
95 views

Constructing a periodic piecewise (piecemeal) function in Maple.

I'm trying to make a piecewise function that will have period $12$. That is, it repeats every $12$ units across the $x$-axis. I managed to do one cycle successfully with ...
0
votes
3answers
790 views

prove transitivity property congruence mod m

Prove transitivity property of congruence mod m. Show that if $x\equiv y \pmod m$ and $y \equiv z\pmod m$ then $x\equiv z\pmod m$ . I didn't really get the tutors explanation of this, I get what ...
0
votes
1answer
40 views

What is the smallest number of times that the digit 1 can appear in N?

All the digits of the positive number $N$ are either $0$ or $1$. The remainder after dividing $N$ by $37$ is $18$. What is the smallest number of times that the digit $1$ can appear in $N$? I have ...
4
votes
2answers
125 views

Solving $x^2 - 11y^2 = 3$ using congruences

I'm looking to find solutions to $x^2 - 11y^2 = 3$ using congruences. The question specifically asks "Can this equation be solved by congruences (mod 3)? If so, what is the solution? (mod 4) ? (mod ...
3
votes
4answers
128 views

Remainder when $11^{2402}$ is divided by $3000$? [closed]

What is the remainder when $11^{2402}$ is divided by $3000$? I just came across this question. I am a beginner in number theory. Your help would mean a lot.Thanks!!
0
votes
5answers
89 views

How I can find the result of $1761^3 \bmod 7$?

I would like to know how I can find the result of $1761^3 \bmod 7$. Is there any rule? Thanks so much for your help!
4
votes
2answers
302 views

Sum of two squares modulo p

I have heard somewhere that for all primes $p$, for all $k$, there exist $x, y$ s.t. $x^2 + y^2\equiv k \pmod{p}$? I recall that the proof is very elementary, but I can't remember such a proof. How ...
1
vote
3answers
73 views

Show that $a^2 \bmod b = (a \bmod b)^2 \bmod b$

Show that $$a^2 \mathrm{\ mod \ } b = (a \mathrm{\ mod \ } b)^2 \mathrm{\ mod\ } b$$ for $ a, b \in \mathbb{Z}^+ $. this was derived from an Informatics olympiad question.
1
vote
2answers
18 views

Help with Understanding Congruence Statement in Divisibility Proof

I am trying to understand the proof of a divisibility rule from this website. I've had very little exposure to modular arithmetic, so in order to attempt to understand the proof I spent the afternoon ...
1
vote
3answers
161 views

How to solve this modular equation? $x^{19} \equiv 36 \mod 97$.

How to solve the following? $x^{19} \equiv 36 \mod 97$. I am having trouble figuring this out. Which technique do I need to use? Chinese Remainder or Fermat's Little Theorem?
1
vote
4answers
82 views

how do you find the modular inverse

I need to find out the modular inverse of 5(mod 11), I know the answer is 9 and got the following so far and don't understand how to than get the answer. I know how to get the answer for a larger one ...
1
vote
0answers
34 views

In $Z[x]$, which pairs of $a,b$ commute as modulo operators, such that ($c$ mod $a$) mod $b =$ ($c$ mod $b$) mod $a$ for every $c$?

In $Z[x]$, which pairs of $a,b$ commute as modulo operators, such that ($c$ mod $a$) mod $b =$ ($c$ mod $b$) mod $a$ for every $c$? What I got so far is: Clearly the equasion holds for every pair ...
0
votes
2answers
46 views

Negative number modular positive number?

I want to understand how -1 % 5 = 4. I already know that 1 % 5 = 1 and 2 % 5 = 2 and so on. ...
1
vote
1answer
80 views

Digit wise modulo for calculating power function for very very large positive integers

I am writing a code to calculate $P^Q$ where $P$, $Q$ are positive integers which can have number of digits up to $100000$. I want the result as $r = P^Q \pmod{10^9+7}$, where $10^9+7$ is a prime ...
2
votes
2answers
61 views

Non cyclic subgroup of $\mathbb{Z}_5$

Let $H = \{0, 2, 3\} \subset \mathbb{Z}_5$. $H$ is a subgroup of $\mathbb{Z}_5$, since it is closed with respect to addition and with respect to inverses. Given that $\langle 2 \rangle = ...
0
votes
0answers
50 views

Testing for Linear Independence/rank mod m

I am working on cracking a hill cypher using modular linear algebra. Every example I have found online makes a big assumption that is not necessarily the case, and as I see it leaves a lot to be ...
0
votes
1answer
39 views

Proof for a relation

Define a relationship $R$ on $\mathbb{Z}$ by declaring that $xRy$ if and only if $x^2 \equiv y^2 (mod 4)$. Prove that $R$ is reflexive, symmetric and transitive. I'm unsure of where to start with ...
1
vote
4answers
186 views

Why didn't Fermat provide proofs of his theorems?

Apparently Fermat stated but didn't provide proofs of various theorems named after him, including Fermat's little theorem, Fermat's theorem on sums of two squares, Fertmat's polygonal number theorem, ...
1
vote
3answers
69 views

Modulo operation. How to prove it?

I noticed relation between modulo operation and number which is power of two Example I have to calculate $ 3431242341 \mod 2^5 $, which is $ 5 $ but it is equivalent to $ ( 3431242341 \mod 2^9 ) ...
4
votes
2answers
217 views

Binomial Congruence Modulo a Prime

Let $p$ be a prime and $a, b$ natural numbers such that $1 \leq b \leq a$. I am trying to prove that $$\binom{ap}{bp} \equiv \binom{a}{b} \pmod p.$$ Furthermore, I have been tasked with proving that a ...
1
vote
0answers
45 views

Given $m^2\bmod A$ and $m^2\bmod B$, how do you find $m^2 \bmod AB$?

Given $m^2\bmod A$ and $m^2\bmod B$, how do you find $m^2 \bmod AB$? I'm 99% sure this is an application of the Chinese remainder theorem, although my workings do not quite show how it can be ...
0
votes
1answer
53 views

Simplifying the expression $l(m) = 2 m - (m \bmod 2^{n-1}).$

I'm trying to simplify the following expression (I hope to be able to write it in a nicer form) but I cannot. For $m \in \mathbb{N}$ and $n \in \mathbb{N}$, $l(m)$ is defined as $$l(m) = 2 m - (m ...
2
votes
5answers
129 views

How to show $n(n+1)(2n+1) \equiv 0 \pmod 6$?

I've been asked to show that: $n(n+1)(2n+1) \equiv 0 \pmod 6$ I found in a previous question that: $n(n+1)$ was divisible by $2$ and resulted in an even number e.g $n(n+1) \equiv 0 \pmod 2$ so I ...
0
votes
1answer
58 views

Converting infinite base-k expansions into base-j expansions

I understood the method of transforming a finite sized base-k numbers to another base (j) through the use of successive divisions For example $$12_{10} = 12/2 + 0*2^0 = 6/2 + 0*2^1 + 0*2^0 = 3/2 + ...
0
votes
2answers
58 views

Why 3 is a multiplicative inverse of 7 in modular arithmetic?

why is 3 a multiplicative inverse of 7 in modular arithmetic of 5 ? I'm not able to understand how this is true. PS: I know 3*7-1 % 5 = 0. I'm not able to make sense of inverses in modular ...
2
votes
0answers
107 views

“Remainder” operation in mod 2^32

I debated posting this here, in the cryptography SE, or the programming SE. Obviously, I chose here, but I'm not confident in my choice... I'm attempting to "undo" a function, but I've hit a slight ...
0
votes
1answer
44 views

What is the fastest way to find a number $n$ based on modular properties of $n$?

How do you find "intersection"s of moduli? For example what is the fastest way to find a number $n$ based on modular properties of $n$? Ex: Find is the first number $n$ such that: $n \equiv 2 \mod ...
0
votes
1answer
37 views

Prove $\alpha: \mathbb{Z_n} \rightarrow \mathbb{Z_n}$ defined by $\alpha(s)=rs\mod{n}$ is an automorphism.

I'm working on proving the following claim: "Let $r \in U(n)$ and $\forall s \in \mathbb{Z_n}$, $\alpha: \mathbb{Z_n} \rightarrow \mathbb{Z_n}$ defined by $\alpha(s)=rs\mod{n}$ is an automorphism." ...
2
votes
5answers
98 views

What is remainder when $5^6 - 3^6$ is divided by $2^3$ (method)

I want to know the method through which I can determine the answers of questions like above mentioned one. PS : The numbers are just for example. There may be the same question for BIG numbers. ...
0
votes
1answer
68 views

Modulo Quadratic Polynomials

Can you, given a large number N, find a, b, c such that ax^2 + bx + c = 0 has at least N roots? All of this is in any mod you choose.
-1
votes
3answers
117 views

Prove that $n^2 + 1$ is not a multiple of $6$ for any positive integer $n$

Prove that $n^2+1$ is not a multiple of $6$ for any positive integer $n$. I i think prime factorization would be a good way to go about this problem but I need some help.
0
votes
3answers
34 views

Prove if $n \equiv 2 \pmod 7$, then $7 \mid (n^2 + 10)$

Prove if $n \equiv 2 \pmod 7$, then $7 \mid (n^2 + 10)$. I tried saying since $n \equiv 2 \pmod 7$, then $7 \mid n - 2$. Thus $7 \mid -5( n - 2)$ or $7 \mid -5n + 10$ and $-5n \equiv 10 \pmod ...
9
votes
1answer
196 views

An analogue of Hensel's lifting for Fibonacci numbers

In this question Oleg567 conjectured the following interesting fact about Fibonacci numbers: $$ k\mid F_n\quad\Longrightarrow\quad k^d\mid F_{k^{d-1}n} $$ that can be regarder as an analogue of the ...
60
votes
4answers
4k views

Fibonacci number that ends with 2014 zeros?

This problem is giving me the hardest time: Prove or disprove that there is a Fibonacci number that ends with 2014 zeros. I tried mathematical induction (for stronger statement that claims that ...
0
votes
2answers
145 views

Congruence modulo primes or in a polynomial ring over ${\rm GF}(2)$

Let $p, q$ be primes. Then the linear congruence $$ap \equiv r\pmod q$$ can be solved for $a\in\mathbb Z$ and will have a unique solution for each value of $r$ such that $0\leqslant a<q$. Am I ...
1
vote
2answers
66 views

Show that if $a^h ≡ 1\mod p$ then $ a^{ph} ≡ 1 \ \mod p^2$.

I don't know how to proceed. I know that regardless of what h is, it divides the order of a modulo $p$. I also know that the order of a divides $\phi(p) \ \text{mod} \ p$, where $\phi$ is Euler's ...
0
votes
3answers
57 views

x≡1 (mod 8) x≡9 (mod 12) has solution x = x_0. How many solutions mod 24 are there to the system of congruences?

Say, x≡1 (mod 8) x≡9 (mod 12) has solution x = x_0. How many solutions mod 24 are there to the system of congruences? I am worried this question is too easy to be true. That is why I am confused. ...
1
vote
5answers
71 views

Direct proof using modular arithmetic

Give a direct proof of $8\mid (3^n + 5^n)$ for all odd natural numbers. I know how to prove this by induction, I am not sure how to go about it using a direct proof. I would start by saying that ...
0
votes
1answer
50 views

Congruence and percentage

Suppose I have three statements of congruence: x = a mod n, y = b mod m, z = c mod p; Furthermore, x is a given percent of x + y + z, as is y and z. Does this uniquely determine x, y, z? Or does it ...
0
votes
3answers
41 views

Proof for a non-conditional statement

I'm having a bit of trouble doing this proof. If $a\in\mathbb{Z}$, then $a^3 \equiv a \pmod 3$. I know how to do proofs if there were conditional statements but not sure how to prove this with ...
1
vote
1answer
74 views

factoring polynomials in $\Bbb Z/11\Bbb Z$

Any ideas as in how to Factor $x^{10}-1$ into linear factors in the integers modulo $11$, $\Bbb Z_{11}=\Bbb Z/11\Bbb Z$? I've been trying but can't come up with an answer.
1
vote
2answers
40 views

modulo group defined by an algebraic relation

I am asked if $\{n, n^{2}, n^{3}\}$ forms a group under multiplication modulo $m$ where $m = n + n^{2} + n^{3}.$ As an example we see that $\{2, 4, 8\}$ does form a group modulo $14,$ with identity ...
1
vote
3answers
76 views

Additive identity in $\mathbb{Z}_{7}$

The problem consists of two parts: 1)Prove that for some integer $m,$ $3^{m} = 1$ in the integers modulo 7, $\mathbb{Z}_{7}$, which i have done. The second part asks to use this fact to deduce that ...
7
votes
1answer
76 views

Matrix restoring (modulo n)

Let $m,n\geqslant 2$, and $A\in \mathcal{M}_n(\mathbb Z)$ such that $\det A \equiv 1 \pmod m$. Does it (necessarily) exist $M\in \mathrm{GL}_n(\mathbb Z)$ such that $A\equiv M \pmod m$?
1
vote
2answers
66 views

How to solve this $ (7/2)\bmod5$?

I know its answer is $3\cdot5$ but I want to ask that is the following true- $$(a/b)\bmod(p) = (a\bmod(p))\cdot((1/b)\bmod(p)))\bmod(p)$$ (where $a$ and $b$ are any integers and $p$ is a prime ...