Stack Exchange Network

Stack Exchange network consists of 175 Q&A communities including Stack Overflow, the largest, most trusted online community for developers to learn, share their knowledge, and build their careers.

Visit Stack Exchange

Questions tagged [modular-arithmetic]

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 $a-b$.

85
votes
9answers
11k 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, ...
35
votes
8answers
13k views

Why is $a^n - b^n$ divisible by $a-b$?

I did some mathematical induction problems on divisibility $9^n$ $-$ $2^n$ is divisible by 7. $4^n$ $-$ $1$ is divisible by 3. $9^n$ $-$ $4^n$ is divisible by 5. Can these be generalized as $a^n$ $-$...
33
votes
8answers
5k views

Linear diophantine equation $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 ...
16
votes
3answers
4k views

Solving simple congruences by hand

When I am faced with a simple linear congruence such as $$9x \equiv 7 \pmod{13}$$ and I am working without any calculating aid handy, I tend to do something like the following: "Notice" that adding $...
7
votes
3answers
695 views

mod Distributive Law, factoring $\!\!\bmod\!\!:$ $\ ab\bmod ac = a(b\bmod c)$

I stumbled across this problem Find $\,10^{\large 5^{102}}$ modulo $35$, i.e. the remainder left after it is divided by $35$ Beginning, we try to find a simplification for $10$ to get: $$10 \equiv ...
6
votes
2answers
8k views

Modulus of Fraction

I just want to confirm I am doing this problem correctly. The problem asks to compute without a calculator: $$ 3 * \frac{2}{5} \pmod 7 $$ The way I am solving the problem: $$ 3 * \frac{2}{5} \bmod 7 \...
29
votes
5answers
8k views

Fibonacci modular results $\ F_n\mid F_{kn},\,$ $\, \gcd(F_n,F_m) = F_{\gcd(n,m)}$

Can any one give a generalization of the following properties in a single proof? I have checked the results, which I have given below by trial and error method. I am looking for a general proof, which ...
66
votes
6answers
10k views

Why is $9$ special in testing divisiblity by $9$ by summing decimal digits? (casting out nines)

I don't know if this is a well know fact but I have observed that every number no matter how large that is equally divided by $9$, will equal $9$ if you add all the numbers it is made from until there ...
94
votes
11answers
29k views

Is zero odd or even?

Some books say even numbers start from two but if you consider the number line concept, I think zero ($0$) should be even because it is in between $-1$ and $+1$ (i.e in between two odd numbers). What ...
7
votes
7answers
541 views

Solving $ax \equiv c \pmod b$ efficiently when $a,b$ are not coprime

I know how to compute modular multiplicative inverses for co-prime variables $a$ and $b$, but is there an efficient method for computing variable $x$ where $x < b$ and $a$ and $b$ are not co-prime, ...
17
votes
2answers
5k views

Order of an Element Modulo $n$ Divides $\phi(n)$

How can I show that the order of an element modulo $n$ divides $\phi(n)$? I know that if $a$ and $n$ are relatively prime, then the least positive integer $x$ such that $a^x\equiv1\pmod n$ is its ...
6
votes
6answers
1k views

How to find last two digits of $2^{2016}$

What should the 'efficient' way of finding the last two digits of $2^{2016}$ be? The way I found them was by multiplying the powers of $2$ because $2016=1024+512+256+128+64+32$. I heard that one way ...
12
votes
5answers
10k views

Prove that $(n-1)! \equiv -1 \pmod{n}$ iff $n$ is prime [Wilson's Theorem]

How can I show that $(n-1)!$ is congruent to $-1 \pmod{n}$ if and only if $n$ is prime? Thanks.
2
votes
2answers
2k 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 ...
24
votes
6answers
14k views

If $n\ne 4$ 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. ...
3
votes
6answers
1k 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\pmod{26}$ If anyone could point me to the solution I'd be grateful, thanks in advance
7
votes
3answers
4k 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 ...
81
votes
3answers
117k 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
3
votes
1answer
409 views

When a congruence system can be solved?

How to prove that a congruence system with $n$ equations can be solved if and only if all the equations can be solved two by two? \begin{cases} x \equiv a_1 \phantom ((mod\phantom mm_1) \\ x \equiv ...
56
votes
7answers
136k views

How to find the inverse modulo m?

For example: $$7x \equiv 1 \pmod{31} $$ In this example, the modular inverse of $7$ with respect to $31$ is $9$. How can we find out that $9$? What are the steps that I need to do? Update If I have ...
28
votes
17answers
50k views

How to Prove the divisibility rule for $3$

The divisibility rule for $3$ is well-known: if you add up the digits of $n$ and the sum is divisible by $3$, then $n$ is divisible by three. This is quite helpful for determining if really large ...
12
votes
4answers
31k 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 ...
22
votes
5answers
76k views

How do you calculate the modulo of a high-raised number?

I need some help with this problem: $$439^{233} \mod 713$$ I can't calculate $439^{223}$ since it's a very big number, there must be a way to do this. Thanks.
4
votes
2answers
1k 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 ...
10
votes
4answers
14k 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 $$ \...
4
votes
3answers
820 views

Mod of numbers with large exponents [duplicate]

I've read about Fermat's little theorem and generally how congruence works. But I can't figure out how to work out these two: $13^{100} \bmod 7$ $7^{100} \bmod 13$ I've also heard of this formula: $...
7
votes
4answers
12k views

Find the last two digits of $ 7^{81} ?$

I came across the following problem and do not know how to tackle it. Find the last two digits of $ 7^{81} ?$ Can someone point me in the right direction? Thanks in advance for your time.
6
votes
3answers
3k views

Find the last two digits of $3^{45}$

I was wondering if there is a simpler way to find the last to digits of a power such as $3^{45}$. I reduced it modulo 100 to get the answer, which is 43. But I was curious if there was a simpler, or ...
10
votes
3answers
2k views

The last two digits of $9^{9^9}$

I tried to calculate the last two digits of $9^{9^9}$ using Euler's Totient theorem, what I got is that it is same as the last two digits of $9^9$. How do I proceed further?
5
votes
4answers
2k 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 ...
4
votes
2answers
261 views

Show that for any prime $ p $, there are integers $ x $ and $ y $ such that $ p|(x^{2} + y^{2} + 1) $.

So we obviously we want $ x^{2} + y^{2} + 1 \equiv 0 ~ (\text{mod} ~ p) $. I haven’t learned much about quadratic congruences, so I don’t really know how to go forward. I suppose you can write it as $...
3
votes
3answers
560 views

last two digits of $14^{5532}$?

This is a exam question, something related to network security, I have no clue how to solve this! Last two digits of $7^4$ and $3^{20}$ is $01$, what is the last two digits of $14^{5532}$?
11
votes
2answers
1k views

Are integers mod n a unique factorization domain?

I am trying to learn abstract algebra from scratch, jolly stuff, but in the process of doing so this puzzles me: Having a ring of integers mod $n$, where $n=pq$ is composite, as I understand we have ...
97
votes
6answers
7k 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 ...
26
votes
5answers
3k views

Number of consecutive zeros at the end of $11^{100} - 1$.

How many consecutive zeros are there at the end of $11^{100} - 1$? Attempt Trial and error on Wolfram Alpha shows using modulus shows that there are 4 zeros (edit: 3 zeros, not 4). Otherwise, I have ...
6
votes
4answers
4k 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}$$
0
votes
4answers
2k 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 ...
12
votes
3answers
3k 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 ...
5
votes
3answers
2k views

If $p$ is congruent to $2 \pmod 3$, how can I prove that all $a$, $1 \le a \le p-1$ are cubic residues $\mod p$?

If $p$ is congruent to $2 \pmod 3$, how can I prove that all $a$, $1 \le a \le p-1$ are cubic residues $\mod p$? Here's what I've done: $1^3$ congruent to $1 \pmod p$ thus, 1 is a cubic residue, ...
6
votes
5answers
680 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}$.
5
votes
1answer
1k 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, $...
8
votes
3answers
4k views

Show that if $a \equiv b \pmod n$, $\gcd(a,n)=\gcd(b,n)$

My problem is how to somehow relate the the gcd and congruence. I know that $(a,b) = ax + by$. I also know that $a \equiv b \pmod n$ means $n\mid a-b$. Any hints? Thanks!
7
votes
1answer
165 views

$N$'s base-5 and base-6 representations, treated as base-10, yield sum $S$. For which $N$ are $S$'s rightmost two digits the same as $2N$'s?

Bernardo chooses a three-digit positive integer $N$ and writes both its base-5 and base-6 representations on a blackboard. Later LeRoy sees the two numbers Bernardo has written. Treating the two ...
10
votes
3answers
3k views

Divisibility rules and congruences

Sorry if the question is old but I wasn't able to figure out the answer yet. I know that there are a lot of divisibility rules, ie: sum of digits, alternate plus and minus digits, etc... but how can ...
5
votes
3answers
3k 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$.
1
vote
2answers
243 views

How many solutions of $\mod 63$ : $x^2=1 \pmod7 $ and $x^3=1\pmod 9$ [closed]

How many solutions $\mod 63$ , we have for: $$x^2=1 \pmod 7$$ and $$x^3=1 \pmod 9$$ Need to find them also.
3
votes
0answers
2k views

$ 1^k+2^k+3^k+…+(p-1)^k $ always a multiple of $p$? [closed]

I would appreciate if somebody could help me with the following problem: Q: For any prime number $p(p\geq 3), k=1,2,3,...,p-2$, why is $$ 1^k+2^k+3^k+...+(p-1)^k $$ always a multiple of $p$ ?
17
votes
5answers
4k views

Is it true that the Fibonacci sequence has the remainders when divided by 3 repeating?

About this Fibonacci sequence, is it true that the remainders when divided by three repeat along with the sequence like this: Fibonacci sequence: $1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233, 377,...
7
votes
5answers
4k 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 ...
10
votes
2answers
3k 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 ...