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

9
votes
4answers
1k views

solve $100x - 23y = -19$

I need help with this equation $$100x - 23y = -19.$$ When I plug this into Wolfram|Alpha, one of the integer solutions is $x = 23n + 12$ where $n$ is a subset of all the integers, but I can't seem to ...
10
votes
4answers
1k views

How do I compute $a^b\,\bmod c$ by hand?

How do I efficiently compute $a^b\,\bmod c$: When $b$ is huge, for instance $5^{844325}\,\bmod 21$? When $b$ is less than $c$ but it would still be a lot of work to multiply $a$ by itself $b$ times, ...
1
vote
2answers
674 views

Getting an X for Chinese Remainder Theorem (CRT)

how do I get modulo equations to satisfy a given X in CRT. For example say I have X = 1234. I choose mi as ...
13
votes
5answers
3k views

If $n$ is composite, then $n$ divides $(n-1)!$.

I have a proof and need some feedback. It seems really obvious that the statement is true but it is always the obvious ones that are a little trickier to prove. So I would appreciate any feedback. ...
7
votes
4answers
4k views

Modular exponentiation using Euler’s theorem

How can I calculate $27^{41}\ \mathrm{mod}\ 77$ as simple as possible? I already know that $27^{60}\ \mathrm{mod}\ 77 = 1$ because of Euler’s theorem: $$ a^{\phi(n)}\ \mathrm{mod}\ n = 1 $$ and $$ ...
22
votes
2answers
25k views

Finding a primitive root of a prime number

How would you find a primitive root of a prime number such as 761? How do you pick the primitive roots to test? Randomly? Thanks
6
votes
4answers
16k views

Calculating the Modular Multiplicative Inverse without all those strange looking symbols

I am sure all those symbols are really easy for you guys to understand, but I would appreciate it if someone could bring it down to earth for me. How could I do this on a basic calculator? or with a ...
6
votes
5answers
316 views

How to solve $100x +19 =0 \pmod{23}$

How to solve $100x +19 =0 \pmod{23}$, which is $100x=-19 \pmod{23}$ ? In general I want to know how to solve $ax=b \pmod{c}$.
1
vote
6answers
154 views

Solving a Linear Congruence

I've been trying to solve the following linear congruence with not much success: 19 congruent to $19\equiv 21x\text{ (mod }26)$ If anyone could point me to the solution i'd be grateful, thanks in ...
3
votes
4answers
910 views

Not understanding Simple Modulus Congruency

Hi this is my first time posting on here... so please bear with me :P I was just wondering how I can solve something like this: $$25x ≡ 3 \pmod{109}.$$ If someone can give a break down on how to do ...
9
votes
2answers
1k views

Very simple question, but what is the proof that x.y mod m == ((x mod m).y) mod m?

I apologise for this question, as it is no doubt very simple, but I've never been very confident with proofs. Our lecturer today (in a course related to maths but not mathematical itself) was playing ...
3
votes
2answers
420 views

Frog Jump Problem

Lotus leaves are arranged around a circle. A Frog starts jumping from one leaf in the manner described below. In the first jump it skips one leaf,next jump it skips two,three the next jump ...
2
votes
3answers
1k views

I don't understand why the inverse is this?

my question is related to matrix inverting and Hill cipher(you don't have to know what it is to help me) My teacher gave me an example. First we have a matrix (the key matrix) that multiplied by a ...
5
votes
3answers
590 views

What will be the one's digit of the remainder in: $\left|5555^{2222} + 2222^{5555}\right|\div 7=?$

What will be the ones digit of the remainder in: $$\frac{\left|5555^{2222} + 2222^{5555}\right|} {7}$$
5
votes
5answers
2k views

Largest integer that can't be represented as a non-negative linear combination of $m, n = mn - m - n$? Why?

This seemingly simple question has really stumped me: How do I prove that the largest integer that can't be represented with a non-negative linear combination of the integers $m, n$ is $mn - m - n$, ...
0
votes
4answers
124 views

Proving Congruence for Numbers

I am working on a problem I am pretty close to solving but I can't figure out the last part. I used some algebraic manipluation to break the problem down. The problem is: Show that the following ...
11
votes
2answers
220 views

Is my shorter expression for $ s_m(n)= 1^m+2^m+3^m+\cdots+(n-1)^m \pmod n$ true?

I'm considering the following sums for natural numbers n,m $$ s_m(n)= \sum_{k=1}^{n-1} k^m =1^m+2^m+3^m+\cdots+(n-1)^m $$ modulo n . Looking at odd n first, I found by analysis of the pattern of ...
4
votes
1answer
613 views

Why is $n\choose k$ periodic modulo $p$ with period $p^e$?

Given some integer $k$, define the sequence $a_n={n\choose k}$. Claim: $a_n$ is periodic modulo a prime $p$ with the period being the least power $p^e$ of $p$ such that $k<p^e$. In other words, ...
-4
votes
2answers
588 views

How many pairs of integers $(A, B)$ are there in the range $[1,\ldots, N]$, such that $\gcd(A,B) = B$?

I am given a positive integer $N$ ($N\leq 10^9$). How many pairs of integers $(A, B)$ exist in the range $[1,\ldots, N]$ such that $\gcd(A,B) = B$?
3
votes
2answers
858 views

$n \mid (a^{n}-b^{n}) \ \Longrightarrow$ $n \mid \frac{a^{n}-b^{n}}{a-b}$

How does one prove that if $n \mid (a^{n}-b^{n}) \ \Longrightarrow$ $ \displaystyle n \mid \frac{a^{n}-b^{n}}{a-b}$ where $a,b, n \in \mathbb{N}$. What i thought of is to consider $$(a-b)^{n} \equiv ...
5
votes
5answers
3k 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: ...
3
votes
2answers
192 views

Solutions of $\prod_{i=1}^n x_i = c$ mod p

The problem is: Given constants $c$ and $n$, how many solutions are there to $\prod_{i = 1}^n x_i = c$ mod p? This is the sort of thing that seems like it should be easy but I really have no idea how ...
1
vote
5answers
2k views

prove that $a \equiv b \mod m$ is an equivalence relation on the integers

prove that $a \equiv b \mod m$ is an equivalence relation on the integers I believe there are 3 properties that it must meet to prove and equivalence relationship. Any reference material would be ...
43
votes
5answers
4k views

Does every prime divide some Fibonacci number?

I am tring to show that $\forall a \in \Bbb P\; \exists n\in\Bbb N : a|F_n$, where $F$ is the fibonacci sequence defined as $\{F_n\}:F_0 = 0, F_1 = 1, F_n = F_{n-1} + F_{n-2}$ $(n=2,3,...)$. How can ...
11
votes
3answers
3k views

Calculate which day of the week a date falls in using modular arithmetic

In Summer Wars the main character (he is a mathematician) calculates the day of the week of someone's birthday (19/07/1992 is Sunday). I know (very) basic modular arithmetic but I can't figure out how ...
7
votes
3answers
1k views

Showing $x^8\equiv 16 \pmod{p}$ is solvable for all primes $p$

I'm still making my way along in Niven's Intro to Number Theory, and the title problem is giving me a little trouble near the end, and I was hoping someone could help get me through it. Now ...
5
votes
3answers
1k views

Chameleons Riddle

There are 10 red, 11 blue, 12 green chameleons. Sometimes, two chameleons meet. If they are the same color, nothing happens. If they are different colors, they will both change to the third ...
2
votes
1answer
1k views

${n \choose k} \bmod m$ using Chinese remainder theorem?

I don't really see too many sites explaining how this is done. Does anyone know how this works? I'm trying to find $\binom{n}{k}\bmod m$, where $n$ and $k$ are large and $m$ is not prime. I think it ...
3
votes
3answers
214 views

Recovering a number from a remainder list

Consider the following list of equations: $$\begin{align*} x \bmod 2 &= 1\\ x \bmod 3 &= 1\\ x \bmod 5 &= 3 \end{align*}$$ How many equations like this do you need to write in order to ...
6
votes
2answers
843 views

Legendre symbol, second supplementary law

$$\left(\frac{2}{p}\right) = (-1)^{(p^2-1)/8}$$ how did they get the exponent. May be from Gauss lemma, but how. Suppose we have a = 2 and p = 11. Then n = 3 (6,8,10), but not $$15 = (11^2-1)/8$$ n ...
3
votes
3answers
281 views

What are $2222^{5555}+5555^{2222} \pmod 7$ and $9^{2n+1}+8^{n+2} \pmod{73}$?

Tell me hint for solve : 1) $ 2222^{5555}+5555^{2222} \equiv \mathord? \pmod 7$ 2) $ 9^{2n+1}+8^{n+2} \equiv \mathord ?\pmod{73}$ thank you.
1
vote
1answer
93 views

In any Pythagorean triplet at least one of them is divisible by $2$, $3$ and $5$.

Show that if $x$, $y$, $z$ are integers such that $x^2 + y^2 = z^2$, then at least one of them is divisible by $2$, at least one is divisible by $3$, and at least one is divisible by $5$. I know that ...
1
vote
5answers
871 views

Solutions of the congruence $x^2 \equiv 1 \pmod{m}$

For $m>2$, if a primitive root modulo $m$ exists, prove that the only solutions of the congruence $x^2 \equiv 1 \pmod m$ are $x \equiv 1 \pmod m$ and $x \equiv -1 \pmod m$. Thanks.
14
votes
5answers
34k views

How to find the inverse modulo m?

For example: $$7x \equiv 1 \pmod{31} $$ In this example, the inverse of $7$ is $9$. How can we find out that $9$? What are the steps that I need to do? Update If I have a general modulo equation: ...
25
votes
5answers
4k views

Prove that every year has at least one Friday the 13th

Everyone knows Friday the 13th is regarded as a day of bad luck. Why does every year have at least one of this bad day?
4
votes
3answers
745 views

The last 2 digits of $7^{7^{7^7}}$

What is the calculation way to find out the last $2$ digits of $7^{7^{7^7}}$? WolframAlpha shows $...43$.
4
votes
4answers
3k views

Difficulty in finding modulus of fraction

It is quite easy to evaluate $\frac{a}{b}\bmod m$ when $a$, $b$ and $m$ are integers and $\gcd(b,m)=1$ by replacing $\frac{1}{b}$ with an inverse of $b$ modulo $m$. But, is it possible to evaluate ...
3
votes
1answer
169 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 ...
2
votes
5answers
485 views

Quadratic congruence and primitive roots

From Apostol Chapter $10$ q$6$: Assume $m>2$, $(a,m)=1$ and there exists an $x$ such that $x^2\equiv a \pmod m$. Prove that $x^2\equiv a \pmod m$ has exactly two solutions iff $m$ has a primitive ...
1
vote
4answers
209 views

Find the last two digits of 9^(9^9) [duplicate]

I want to find the last two digits of $9^{9^9}$, that is $9$ raised to the power $9^9$. I tried using Euler's theorem but I can't make anything of it. As always, I ask only for a minor hint, not a ...
0
votes
5answers
187 views

Proving that if $\;5\mid(a+11)\;$ and $\;5\mid(16-b),\;$ then $\;5\mid(a+b)$

Can you please help me a bit with this question? How do we show that $\;$ if $\;\;5\mid(a+11)\;$ and $\;5\mid(16-b),\;\;$ then $\;5\mid(a+b)\;$? Thanks a lot!
0
votes
2answers
416 views

Number of solutions of $ax \equiv b \mod n$

I want to solve $ax \equiv b \mod n$ given a solution $x_0$. How can i prove that there are exactly $(a,n)$ solutions ?
0
votes
1answer
410 views

Accuracy of Fermat's Little Theorem?

If $a^{N-1} \neq 1\pmod{N}$ for some $a$ relatively prime to $N$, then must the equality fail for at least half the choices of $a<N$ Could someone provide proof for this statement?
-1
votes
1answer
100 views

Modular Arithmetic - Evaluate/Find Square roots

Okay so I have three types of questions here that I do not know how to do. Could someone please tell me how I would go about solving these? I would greatly appreciate it Evaluate a square root of 3 ...
48
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 ...
28
votes
1answer
762 views

Is $\sqrt1+\sqrt2+\dots+\sqrt n$ ever an integer?

Related: Can a sum of square roots be an integer? Except for the obvious cases $n=0,1$, are there any values of $n$ such that $\sum_{k=1}^n\sqrt k$ is an integer? How does one even approach such ...
48
votes
8answers
3k views

The last digit of $2^{2006}$

My 13 year old son was asked this question in a maths challenge. He correctly guessed 4 on the assumption that the answer was likely to be the last digit of $2^6$. However is there a better ...
11
votes
5answers
326 views

Why are there$ 736$ $2\times 2$ matrices $(M)$ over $\mathbb{Z}_{26}$ for which it holds that $M=M^{-1}$?

I'm currently trying to introduce myself to cryptography. I'm reading about the Hill Cipher currently in the book Applied Abstract Algebra. The Hill Cipher uses an invertible matrix $M$ for ...
6
votes
5answers
352 views

Basic question about mod

I'm having a tough time understanding why $(a^x \bmod p)^y \bmod p$ is equal to $a^{xy}\bmod p$. Does this have a mathematical proof? Please advise.
5
votes
1answer
137 views

Primes for which $x^k\equiv n\pmod p$ is solvable: the fixed version

For fixed $n$ and $k$, how can I characterize the primes $p$ such that $x^k\equiv n\pmod p$? Less important to me: Is there a similar characterization for composite moduli? Assume the factorization ...