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

3
votes
2answers
61 views

Finding $23! 7! \bmod 29$ using Wilson's Theorem

I'm trying to reduce $23!\,7! \bmod 29$. I used Wilson's Theorem to get $23!(120)\equiv 1 \pmod{29}$. I then solved $120a\equiv 1 \pmod{29}$ and got $a\equiv 22$. I then computed $7! \pmod {29}$. ...
0
votes
1answer
36 views

Sequence That increases and then decreases using Modular Arithmetic

I'm trying to find a simple formula for a periodic sequence like this: $$ 0,1,2,3,4,3,2,1,0...$$ I've figured it out for the increasing part of the sequence by using a modulo operator: $$ i\ mod \ ...
0
votes
2answers
30 views

Simplifying modulus expressions and an unknown expression? discrete math

I have a few questions below that I need help with a) I don't really understand what that symbol means and how to solve it b) How do u simplify this without a calculator c) I got 2^-r = 0, iss this ...
5
votes
3answers
104 views

How to prove that $53^{103}+ 103^{53}$ is divisible by 39?

This is a problem in my number theory textbook. It is based on modular arithmetic but im not getting how to start off to prove this. Please give me some hints on how to solve it.
1
vote
4answers
46 views

How to find the remainder when the following series is divided by 12? [duplicate]

$1! + 2! + 3!+\cdots + 99! + 100!$ I am not getting any idea on how to solve this problem. I know that modular arithmetic should be used but not getting how to start off with the solution. Please ...
1
vote
2answers
41 views

Proof that the congruence relation on $\mathbb Z$ is transitive (attempt shown)

I have answered this question to the best of my knowledge but somehow I feel as if I am missing something? Can I further prove this statement or add anything to it? Question: Let $m \in \mathbb ...
-1
votes
1answer
15 views

Equivalance class in modulus [on hold]

How many equivalence class are there for the modulus 7? I referred wikipedia (http://en.wikipedia.org/wiki/Modular_arithmetic) , But could not find the answer. Can some one help.
1
vote
3answers
46 views

How to solve a pair of simultaneous linear congruences, using algebraic methods [on hold]

What is the smallest whole number $x$ so that $x$ has remainder $14$ when divided by $400$, and $x$ has remainder $5$ when divided by $7572$? In other words: $$x \equiv 14 \pmod{400}$$ and $$ ...
3
votes
3answers
61 views

Raising $2$ to the power of $2014^ {2013}$ modulo $41$

The question is as follows: $$2^{{2014}^{2013}}$$ Determine its remainder by division with $41$. I know that I need to use $\bmod 41$ and reduce the power somehow to something that can be solved ...
0
votes
2answers
48 views

Modular algebra problems

I got some problem with those demonstrations and I don't know where I'm wrong, let me show you my steps: 1: first of all $ 6 | 2n(n^2 +2) $ That is, I must demonstrate that $6$ divides $2n(n^2 ...
0
votes
3answers
58 views

modules with several powers $x^{y^z}$

I have an assignment(which gives no credit) which I cant solve so I would like to get some help $3^{{1001}^{1002}}\pmod {43}$ (All original numbers were replaced) Our hint was to use the ...
0
votes
0answers
32 views

$x^2 \equiv a \pmod p$ but $xy \not\equiv a \pmod p$

Let there be a natural number $k$. A set $X$ is of cardinality $k$, and elements of $X$ are integers. For every $k$, does there exist prime number $p$ such that $$\forall x \in X,\ x^2 \equiv a ...
1
vote
1answer
56 views

Find $n$ between $100$ and $1000$ so that $2^n+2$ is divisible by $n$

Find $n$ such that $n$ divides $2^n + 2$. Also, $n$ should be between $100$ and $1000$. It can be easily seen that $n$ is not a multiple of $4$. By brute force I have figured out that answer is ...
2
votes
4answers
47 views

Reduction modulo p

I am going to begin the Tripos part III at Cambridge in October (after going to a different university for undergrad) and have been preparing by reading some part II lecture notes. Here is an extract ...
1
vote
2answers
40 views

Problem involving summation and binomial coefficient

I have been fighting with this but I'm really not getting anywhere. $$\sum_{0\leq2k\leq n}\binom{n}{2k}2^k\equiv0\pmod 3$$ $$iff$$ $$n\equiv2\pmod 4$$ Hint: Consider ...
0
votes
0answers
28 views

Isomorphic matrix groups over rings

I've thinking about this problem for the last couple days and I can't get anywhere. I would really appreciate some help. Is it true that, a) $\operatorname{SL}_n(\mathbb{Z}/2013\mathbb{Z})\cong ...
0
votes
1answer
37 views

Modular arithmetic and linear congruences

Assuming a linear congruence: $ax\equiv b \pmod m$ It's safe to say that one solution would be: $x\equiv ba^{-1} \pmod m$ Now, the first condition i memorized for a number $a$ to have an ...
0
votes
0answers
33 views

Negative modulo operations

I am trying to understand modulo operations. Although the result is defined as a remainder for a division process. Confusion arises when the dividend is smaller than the divisor ...
0
votes
0answers
19 views

Congurence proof of modulus equivalence

I would like some advice if I have approached this problem correctly please: let $a,b,m,n \in \mathbb{Z}$ and $m,n > 0$. Prove that if $a\equiv b \pmod n$ and $m|n$, then $a\equiv b\pmod m$ ...
2
votes
3answers
97 views

remainder when 67896789…(300 digits) divided by 999

What is the remainder when 678967896789... (300 digits)is divided by 999? i tried to divide it manually to find some pattern in remainder. But was getting bit lengthy. so please suggest me some short ...
0
votes
2answers
39 views

how many integers satisfy for modular aritmetic

How many integers $n$ are there which satisfy $1\leq n \leq 2014$ and $21n = 25 \pmod {29}$?
1
vote
2answers
40 views

l'th root-ing in modulo arithmetic .

It is clear that $$(x \equiv y \mod{z}) \implies (x^n \equiv y^n \mod{z})$$ It came from the fact that $$(a \equiv b \mod{e})\land(c \equiv d \mod{e})\implies (ac \equiv bd \mod{e})$$ But is it ...
4
votes
4answers
67 views

$a^m + b^n \equiv 1 \mod ab$ for some $m,n$

If $a$ and $b$ are relatively prime integers, then there exist integers $m$ and $n$ such that $a^m + b^n \equiv 1 \mod ab$ . How do I show this to be true? (Artin's Algebra problem 11.1.16)
1
vote
4answers
25 views

How to find a modular multiplicative inverse when GCD is not 1

I am working on a problem that requires finding a multiplicative inverse of two numbers, but my algorithm is failing for a very simple reason: the GCD of the two numbers isn't 1. I figured I must've ...
3
votes
1answer
78 views

Remainder on dividing $10^{n} + 10^{n-1} + … + 10^{1} + 10^{0}$ by x

Given a positive integer $n$, consider the number $y=10^{n}+10^{n-1}+$$...+ 10^{1}+10^{0}$. I need to find the remainder when $y$ is divided by a natural number $x$. e.g. $111111$ $\%$ $2123$ = ...
0
votes
1answer
44 views

Under what conditions can we obtain $a \equiv 1 \pmod{mn}$ from $a \equiv b \pmod{m}$ and $b \equiv 1 \pmod{mn}$?

If $a \equiv b \pmod{m}$ and $b \equiv 1 \pmod{mn}$, are there any conditions under which we can conclude that $a \equiv 1 \pmod{mn}$? Here $m$ and $n$ are any integers; $a$ and $b$ are both coprime ...
1
vote
1answer
48 views

Residue class of a huge repunit modulus a huge number

Given a number with only 1: X = 1111...1 (N times 1 in total), and another number M, I want ...
0
votes
1answer
80 views

How to find out a^b^c^… mod m

I would like to calculate: abcd... mod m I know when a is coprime to m then we can easily find out the answer using Euler's totient function. But I wish to know the ideas when a is not coprime to ...
0
votes
0answers
11 views

Intersections running around a discrete circuit

Imagine two iterators running around a discrete circular track (iteratorA and iteratorB). Say we know the following pieces of information: Size of the track (number of nodes or bases). Speed ...
1
vote
1answer
30 views

Find modular inverse of a number

Recently I have read extended euclid's algorithm which is used to find out the modular inverse of a number N whith respect to MOD such that $\gcd(N,MOD)=1.$ But I have a doubt that how to find modular ...
0
votes
2answers
94 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
79 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
258 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? ...
4
votes
0answers
154 views

Prove modular equivalence related to carmichael function.

Statement if $n=p_1p_2p_3\cdots p_r$ (prime numbers are distinct) and $2 \le a \le n-1$ then prove that $$a^{k\lambda} \equiv \left(1+\sum_{p_i\mid\gcd(a,n)}\left(\dfrac{n}{p_i} \right) ...
0
votes
1answer
67 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 ...
6
votes
0answers
51 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
0answers
11 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
122 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
31 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
4answers
95 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
77 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
106 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
70 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
11 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 ...
2
votes
3answers
82 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
43 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
22 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
0answers
40 views

Average and Standard Deviation for Angular Values

I'm trying to characterize an inexpensive accelerometer that provides (roll, pitch, yaw) values by generating basic running statistics (mean and standard deviation). But I'm unfamiliar with ...
0
votes
1answer
19 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. but please explain this when is is negative as the previous example
1
vote
1answer
35 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 ...