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

2
votes
1answer
137 views

If the dividend is multiplied by a given number, and divided by the same divisor, the new remainder is multiplied by the same number?

In a division, if the (the number which is being divided) is multiplied by certain factor and then divided by the same divisor, then the new remainder will be obtained by multiplying the original ...
0
votes
1answer
29 views

Proof of Floyd Cycle Chasing (Tortoise and Hare)

I am looking for a proof of Floyd's cycle chasing algorithm, also referred to as tortoise and hare algorithm. After researching a bit, I found that the proof involves modular arithmetic (which is ...
3
votes
0answers
40 views

Combinatorial interpretation of an equality

In a recent project, I came up with the following equality which turned out to be extremely useful for counting conjugacy classes in certain division algebras (I won't go into the details here, it's ...
1
vote
3answers
55 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 ...
7
votes
3answers
118 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.
0
votes
0answers
31 views

Primorial mod $2^{32}$

Is $p_n\#$ (primorial - product of $n$ primes) periodic $\pmod{2^{32}}$? It's periodic $\pmod2$ and $\pmod4$, however it don't seems periodic $\pmod8$ and greater modulus.
2
votes
1answer
24 views

Average Number of Roots of a Polynomial modulo p

Let $f \in \mathbb{Z}[X]$ be an irreducible non-constant polynomial, and consider this polynomial modulo $p$ for each prime $p$. On average, how many roots does $f$ have modulo $p$? I.e., if $r(p)$ ...
3
votes
2answers
73 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}$. ...
1
vote
2answers
43 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 ...
5
votes
5answers
2k views

Solving simultaneous congruences

Trying to figure out how to solve linear congruence by following through the sample solution to the following problem: $x \equiv 3$ (mod $7$) $x \equiv 2$ (mod $5$) $x \equiv 1$ (mod $3$) Let: ...
1
vote
1answer
305 views

Solving a non-linear congruence

How can we solve for $x$, knowing the integer $n$ and the real numbers $a$ and $b$, the following non-linear congruence: $(x+a)^2=-b\pmod{n}$ Specifically in this example: ...
0
votes
2answers
35 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 ...
0
votes
1answer
35 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 ...
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 \ ...
1
vote
4answers
47 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
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
48 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
67 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 ...
2
votes
4answers
85 views

Proving congruence modulo, number theory

The task is to prove $24^{31}\equiv 23^{32}\pmod {19}$. I'm trying to use Fermat's little Theorem and so far I only found that $24^{31}\equiv 19\pmod{19}$. Would proving that $17\mid23^{32}$ prove ...
0
votes
3answers
59 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 ...
1
vote
1answer
58 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 ...
0
votes
2answers
49 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
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 ...
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 ...
-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? ...
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
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
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$ ...
4
votes
0answers
155 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) ...
2
votes
3answers
102 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
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
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
41 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
69 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
49 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 ...
1
vote
1answer
63 views

$\mathbb Z_n$ modular tables , invertible elements and zero/nonzero divisors

Based on $\mathbb Z_n$, with $n\leq10$, make a guess about which elements in $\mathbb Z_n$ are invertible and which are nonzero divisors. Does your guess imply that every nonzero element is either ...
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 ...
0
votes
2answers
96 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$.
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 ...
4
votes
1answer
134 views

Fast way to find the smallest root $\mod M$ of a polynomial

Suppose you're given a polynomial of degree $d$ with integer coefficients: $$ P(x) = \sum_{i=0}^{d}{a_i x^i} $$ Is there a fast way to find the smallest root modulo $M$, where $M$ is some composite ...
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 ...
45
votes
4answers
3k 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 ...
1
vote
2answers
509 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?
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 ...