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

6
votes
4answers
919 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 ...
1
vote
2answers
624 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 ...
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, ...
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 $$ ...
17
votes
2answers
20k 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
14k 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 ...
13
votes
5answers
2k 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. ...
6
votes
5answers
308 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}$.
3
votes
4answers
861 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 ...
3
votes
2answers
313 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 ...
9
votes
2answers
907 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 ...
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
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
94 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
209 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
580 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, ...
3
votes
2answers
834 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
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: ...
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 ...
-4
votes
2answers
563 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$?
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 ...
6
votes
3answers
948 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 ...
2
votes
1answer
997 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
205 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 ...
4
votes
2answers
694 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
280 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
5answers
713 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.
41
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 ...
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
2answers
419 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}$$
4
votes
4answers
2k 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 ...
2
votes
5answers
465 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 ...
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
1answer
364 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
85 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 ...
44
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
714 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 ...
45
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 ...
12
votes
5answers
29k 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: ...
11
votes
5answers
317 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 ...
5
votes
3answers
887 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 ...
6
votes
5answers
349 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.
4
votes
1answer
126 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 ...
1
vote
1answer
43 views

Negative quotients and their remainders

Since $16 \div{-3} = -5.\overline{3}$, I thought I could also express this as $16 \div{-3} = -5\:R\:1$ or in other words $16\mod{-3} = 1$. My calculator tells my it is in fact $-2$. Along the same ...
4
votes
2answers
659 views

Prove that $x^{2} \equiv -1$ (mod $p$) has no solutions if prime $p \equiv 3\pmod 4$.

Assume: $p$ is a prime that satisfies $p \equiv 3 \pmod 4$ Show: $x^{2} \equiv -1 \pmod p$ has no solutions $\forall x \in \mathbb{Z}$. I know this problem has something to do with Fermat's Little ...
3
votes
5answers
565 views

Modular Inverses

I'm doing a question that states to find the inverse of $19 \pmod {141}$. So far this is what I have: Since $\gcd(19,141) = 1$, an inverse exists to we can use the Euclidean algorithm to solve for ...
3
votes
2answers
601 views

Using Fermat's little theorem

I have this question: $a \equiv 12^{772} \pmod{71}$, when $0 \leq a < 71$ and I am having troubles getting it started. $\frac{772}{71}$ is $10$ with a remainder of $62$; How do I do this ...
2
votes
3answers
233 views

Find the values of $p$ such that $\left( \frac{7}{p} \right )= 1$ (Legendre Symbol)

Show that if $p$ is an odd prime coprime to $7$, then $\left( \frac{7}{p} \right) = 1$ if and only if $p \equiv \pm 1, \pm 3,$ or $\pm 9 \pmod{28}$. HINT: If $p$ is an odd prime, determine which ...
2
votes
5answers
869 views

finding inverse of $x\bmod y$

I am working through a review problem asking to find the inverse of $4\bmod 9 $. Through examples I know that I first need to verify that the gcd is equal to 1 and write it as a linear combination of ...
1
vote
2answers
122 views

determining order of $x+1$ given the $x$ has order three

I was trying to expand $(x+1)^n$, then plug $x^3$ in to the expansion of the $(x+1)^n$, keep trying it until I get the order, are there any other ways? So if $x^3\equiv 1\pmod y$, how would I ...