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

1
vote
3answers
118 views

If $n$ is an integer then $\gcd(2n+3,3n-2)=1\text{ or ?} $

There are two possible Gcd's for integers of the form, $2n+3$ and $3n-2$ I know the gcd is $1$ if I take the equation modulo $2$. However if I take the equation modulo $3$ I get, $2n$ and $-2$. ...
4
votes
4answers
169 views

What is the smallest positive integer of the form $30x+6y+10z$? [closed]

I am trying to find the smallest positive integer of the form $30x+6y+10z$, where $(x,y,z)\in\mathbb{Z}$ However, I do not know where to start. Hints or answers are welcome. Thanks!
1
vote
2answers
64 views

Is such modulus trick possible?

If we have a result of $a \pmod {10^{100} + 7}$ or $a \pmod {10^{100} + 1}$ without knowing what $a$ is, is there a way to get a result of $a \bmod 10^{100}$?
0
votes
1answer
44 views

Modular Congruence, Power

$(3x^2+2x+1)(4x^3+x^2+5x+1)=5x^5+4x^4+1\equiv 1 \pmod {x^4}$ Expanding the first part, I get $12x^5+11x^4+21x^3+14x^2+7x+1$. However, I do not understand how to get from the above statement to ...
11
votes
3answers
290 views

Finding $n$ satisfying $\{1^n-0^n,2^n-1^n,\cdots,p^n-(p-1)^n\}\equiv \{0,1,\cdots,p-1\}\pmod p$

Background : About a month ago, a friend of mine taught me his findings about a few polynomials which cover all the residue classes in mod $p$ where $p$ is a prime. Then, I began to consider the same ...
0
votes
1answer
365 views

Who to solve this linear modular equation system?

I have this equation system: a + b + c (mod 11) = 8 9a + 3b + c (mod 11) = 2 16a + 4b + c (mod 11) = 9 Unfortunately I totally don't know how to solve it. It is in general part of Lagrange's ...
2
votes
2answers
290 views

Changing the Modulo congruence base?

This is a conversion someone on SE made: $$77777\equiv1\pmod{4}\implies77777^{77777}\equiv77777^1\equiv7\pmod{10}$$ But I don't understand how this is done?
3
votes
3answers
256 views

Find the last digit of $77777^{77777}$

Find the last digit of $$77777^{77777}$$ I got a pattern going for $77777^n$ for $n=1, 2, ....$ to be: $$7, 9, 3, 1$$ for $n = 1, 2, 3, 4$ respectively. The idea is: $$77777^{77777} \pmod{10}$$ ...
-1
votes
1answer
31 views

Proof involving inverses and modulo

I'm working through an exercise which states: Let a' be the inverse of a modulo m and let b' be the inverse of b modulo m. Prove that a'b' is the inverse of ab modulo m. So far what I have is: We ...
0
votes
0answers
22 views

Modular Exponential non-coprimes

Given a,b,c,p so s.t p is Sophie-germain (p is prime and 2p+1 is prime). How would you solve: (a^b^c) mod (2p). I was thinking, if a is odd, I could use euler toitent function and calcular a^(b^c mod ...
0
votes
1answer
56 views

Why reduce $64\bmod{11}$ down to $12\bmod{11}$?

This is the problem I am currently working on Find this value: $(7^3\bmod{23})^2\bmod{11}$ Here's my work: $$\begin{align*} &(7^3\bmod{23})^2\bmod{11}\\ &64\bmod{11}=9 \end{align*}$$ This ...
2
votes
1answer
704 views

Finding remainder of dividing and moding large exponents [duplicate]

Can anyone explain how to calculate the remainder for types of problems like this: $2^{2131312213123}$ divided by 100 $13^{6601}$ mod 77
1
vote
0answers
55 views

What is the smallest number written as a sum of cubes?

What is the smallest number of the kind $\overline{999a}$, which can be presented as a sum of two natural cubes? ($a$ is a digit). I do NOT multiply below (when I write $999a$) $$999a = x^3 + y^3$$ ...
1
vote
0answers
67 views

Euler's totient function - Why?

I know this one's true, but I can't prove it. I've tried everything. $$a^{b\bmod{(\theta(m))}}\bmod(m)=a^b\bmod(m)$$ Multiply the exponent with $m-1$ (assume $m$ is prime, it doesn't matter anymore) ...
5
votes
2answers
156 views

Prove $717$ is not prime using Wilson's Theorem

Prove that $717$ is not prime using Wilson's Theorem. Assume $717$ is prime then: $$716! \equiv -1 \pmod{717}$$ $$ 716 \cdot 715! \equiv -1 \mod{717}$$ $$ 716 \equiv -1 \pmod{717}$$ $$715! = 715 ...
6
votes
1answer
239 views

Proving $11! + 1$ is prime

Prove that: $$11! + 1$$ is a prime number. Without computing the number (or factorial). Obviously, from Wilson's theorem, a number $n$ is prime if, $$(n-1)! + 1 \equiv 0 \pmod{n}$$ Since $n = ...
1
vote
1answer
66 views

Modular arithmetic - Power

I am dealing with the following question: Given a,b,c,d, p positive integers, I wanna compute a^(b^(c^d)) mod 2p+1. Given that p is sophie-germain. That is, 2p+1 is also prime. Any ideas?
1
vote
1answer
43 views

Let p be prime. Prove that:

Let p be prime: $p^2\choose p$ is congruent to p (mod $p^2$) and $2p\choose p$ is congruent to 2(mod$p^2)$ I know that when p is prime p|$p\choose k$ where $p\choose k$ can be defined as ...
0
votes
2answers
48 views

Modular arithmetic calculation $366^3\pmod {391}$ [closed]

$366^3\pmod{391}$ Is there an easy way to calculate this without a calculator?
1
vote
1answer
80 views

How many subgroups does $\mathbb{Z}_5$ have

How many subgroups does $\mathbb{Z}_5$ have (addition)? here is my Cayley table (sorry for the formatting): $\ \ \ 0\ 1\ 2\ 3\ 4\ \\ 0\ 0\ 1\ 2\ 3\ 4 \\ 1\ 1\ 2\ 3\ 4\ 0 \\ 2\ 2\ 3\ 4\ 0\ 1 \\ 3\ 3\ ...
2
votes
2answers
52 views

How is this a field?

From Stephen Abbott's - understanding analysis there is a section in the text which says: "The finite set $\{0,1,2,3,4\}$ is a field when addition and multiplication are computed modulo 5." I ...
4
votes
1answer
115 views

Prove $2^{1092}\equiv 1 \pmod {1093^2}$, and $3^{1092} \not \equiv 1 \pmod {1093^2}$

I did try to factorise 1092 and it is equal to $2^2*3*7*13$ and I really don't know what I can do with this. Do I need to calculate all the powers?
7
votes
1answer
151 views

Is The Statement $b^n\equiv 1\pmod n$ equivalent to “$x\mapsto b^x-x\pmod n$ is a bijection”?

Suppose that $n$ is a natural number and $b$ is one coprime to it such that $b^n\equiv 1\pmod n$. Does it follow that, if $b^x-x\equiv b^y-y\pmod n$, then $x\equiv y\pmod n$? This is inspired by ...
10
votes
3answers
232 views

Number Theory : What are the last three digits of $9^{9^{9^9}}?$

I was doing some basic Number Theory problems and came across this problem and was all thumbs : Find the last three digits of $9^{9^{9^9}}$ How would I go about solving this problem? I am a ...
2
votes
2answers
50 views

Find all numbers of form $10^k+1$ divisible by $49$

Basically, I've tried to take mods, and it hasn't been very successful. Also, if it helps, I noticed that the sequence can be recursively written as $a_{n+1}=10a_n-9$, starting with $a_1=11$.
0
votes
0answers
30 views

Determine when a prime divides this

Let $x$ and $y$ be integers, and consider the expressions $A=192x+a$ and $B=192y+b$, where $a,b$ are nonnegative mod $192$ residues (so $a,b\in \{0,1,2,...,191\}$). For which ordered pairs $(a,b)$ ...
1
vote
0answers
38 views

First ODD primes and modular equation

This is a modular equation involving first $k$ ODD primes: $$ 3^{5+7+11+13+17+\dotsb+p(k-3)+p(k-2)}=p(k-1) \mod p(k) $$ where $p(k)$ is the $k$-th ODD prime number. I've checked $k$ up to $50$, ...
0
votes
2answers
92 views

Where does 2525 and 252525 come from in RSA cryptosystem example?

This is an example from Discrete Mathematics and its Applications I understand how to encrypt, the first step is to turn the letters into their numerical equivalents(same thing we had to do for ...
0
votes
1answer
53 views

How to recover the original text/find decryption function?

This is from Discrete Mathematics and its Applications Here's my book section on shift ciphers. I understand the idea behind this. If you were trying to encrypt say a single letter 'b' with a ...
1
vote
2answers
215 views

What mistake am I making when trying to apply Fermat's little theorem?

This is a problem from Discrete Mathematics and its Applications This is Fermat's little theorem from https://www.youtube.com/watch?v=w0ZQvZLx2KA, Here is my work so far First 41 is prime and ...
1
vote
2answers
49 views

Can someone verify the reasoning of why these two congruences are equivalent?

I've wondered why two congruences like $x\equiv81\pmod {53}$ and $x\equiv28\pmod{53}$ were equivalent. I've come up with this proof. I am not sure if this is how you prove it though I know that ...
0
votes
1answer
28 views

$R = A \times B + C$, How retrieve A and C if C is negative?

For A = 18, B = 54 and $C = {-53, 53}$ $$R = A \times B + C$$ I can retrieve A and C from R with: $$ A = \lfloor R \div B \rfloor $$ $$ C={R} \pmod {B} $$ example, A = 18, C = 53: $$ R = 18 \times ...
2
votes
3answers
75 views

How to find all solutions to system of congruences with Chinese Remainder Theorem?

This is from Discrete Mathematics and its Applications Here is my work so far gcd(3, 4) = 1 $\,$gcd(3, 5) = 1$\,$gcd(4,5) = 1 $\quad$ mod 3 $\quad$ mod 4 $\quad$mod 5 x $\equiv$ 4 * 5$\qquad$3 * ...
1
vote
1answer
38 views

Why doesn't the author straight up multiply the 15 by 2 in Chinese Remainder Theorem?

This is from a Youtube video on the Chinese Remainder Theorem -https://www.youtube.com/watch?v=ru7mWZJlRQg The value at each column is the product of the mod of the two other columns(so moding will ...
8
votes
2answers
174 views

Last digit of $3^{459}$.

I am supposed to find the last digit of the number $3^{459}$. Wolfram|Alpha gives me ...
0
votes
0answers
106 views

How do you find inverse of mod with large exponents?

Something like $2^{125} \pmod {127}$ Would you apply the Extend Euclidean Algorithm?
1
vote
2answers
87 views

Finding inverse of $2\mod 127$?

I can't seem to understand why the inverse of $2 \mod 127=64$ I used the Euclidean algorithm: $2x=1 \mod127$ $127=63\cdot 2+1$ $1=127-63\cdot 2 \mod127$ $x=63$? I'm pretty sure it's a really ...
1
vote
2answers
46 views

Linear congruence fill in the missing step?

Currently working on this problem and I'm having trouble seeing how it goes from one line to the next. $45x \equiv 63\mod 11$ goes to $x \equiv 8\mod 11$ Any help would be awesome thanks. ...
2
votes
1answer
49 views

Why doesn't the author subtract everything by two first before applying modulus?

This is from a youtube video on the Chinese Remainder Theorem - https://www.youtube.com/watch?v=ru7mWZJlRQg What the author has done thus far is basically 1.Make sure that the mods, 3, 4, 5 are ...
1
vote
3answers
83 views

If p is an odd prime, prove that $a^{2p-1} \equiv a \pmod{ 2p}$

Let $m = 2p$ If p is an odd prime, prove that $a^{2p - 1} \equiv a \pmod {2p} \iff a^{m - 1} \equiv a \pmod m$. I have no idea on how to start. I was trying to find a form such that $a^{m - 2} ...
0
votes
6answers
95 views

How to find the multiplicative inverse of $2^{29} \mod 9$

I just started studying this topic and from my understanding I have to find an integer $x$ such that: $2^{29}x \equiv 1 \mod 9$ However, I have no idea of how to find a linear combination of $9$ and ...
0
votes
1answer
121 views

Does someone see my mistake when calculating inverse of 34 mod 89?

This is from Discrete Mathematics and its Applications I am doing 6b. The method in example 2 is basically using Euclid's Algorithm to make sure that the greatest common divisor is 1 and then back ...
0
votes
2answers
65 views

Computing $22^{201} \mod (30)$

I am having trouble, I tried using the fact that the $gcd(30, 22) = 2$ but I have been stuck here for a bit now. $22^{201} \equiv x \mod (30)$ $22^{201} \equiv 22*22^{200} mod (30)$ How can I ...
0
votes
4answers
1k views

How to find inverse of 2 modulo 7 by inspection?

This is from Discrete Mathematics and its Applications By inspection, find an inverse of 2 modulo 7 To do this, I first used Euclid's algorithm to make sure that the greatest common divisor ...
-4
votes
2answers
359 views

How to find all the Quadratic residues modulo $p$

I want to implement Sieve improvement for Fermat's factorization method. For that I need your help answering: How to find all the Quadratic residues modulo $p$? $$\{x ~\vert~ x^2 \equiv q ...
0
votes
2answers
79 views

Can someone clarify the notation of x $\equiv$ -8 $\equiv$ 6 ($\bmod$ 7)

This is an example from Discrete Mathematics and its Applications This is example 1 that this example references And here's Theorem 1 that the example references Example 1 makes sense. We have ...
3
votes
1answer
58 views

Solve modulo equation

Decide whether the equation has solutions and if it does, find them all. $10x \equiv 14 \pmod {17}$ Since $17\mid 10x-14$, $x$ must have the following form $x=\frac{17y+14}{10}$. $x$ belongs ...
1
vote
1answer
27 views

Modulo the square of the rational units

In a book I'm reading the following modulus comes up, $$ \operatorname{mod} \: \mathbb{Q}^{*2}$$ and I'm struggling to understand what it means. I understand $\mathbb{Q}^{*} = \mathbb{Q}\backslash ...
2
votes
4answers
39 views

How did author reach the conclusion tm $\equiv$ 0($\bmod$ m)?

This is a proof of a theorem from my book, Discrete Mathematics and its Applications Here is theorem 6 of Section 4.3 The first part of the proof, "because gcd(a, m) = 1" makes sense because the ...
0
votes
1answer
39 views

How does author reach step of $sa + tm \equiv 1 \pmod m$?

This is a proof of a theorem from my book, Discrete Mathematics and its Applications Theorem 1 If $a$ and $m$ are relatively prime integers and $m>1$, then an inverse of $a$ modulo $m$ ...