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
2answers
83 views

Proving if $a_1\equiv b_1\pmod{n}$ and $a_2\equiv b_2\pmod{n}$ then we have $a_1+a_2\equiv b_1+b_2\pmod{n}$.

How can I prove if $a_1\equiv b_1\pmod{n}$ and $a_2\equiv b_2\pmod{n}$ then we have $a_1+a_2\equiv b_1+b_2\pmod{n}$? I have tried several ideas I've found online but don't really understand them. Is ...
1
vote
1answer
51 views

Formula for working out an ID number by given set of coordinates

I'm designing an online game and having a bit of a mental block coding the navigation system. It's designed on a 2 dimensional grid, each cell has an ID 0...n, n being the total number of cells in the ...
3
votes
2answers
126 views

Help with proof of showing idempotents in set of Integers Modulo a prime power are $0$ and $1$

I was reading online for a project I'm currently doing and came across the following claim and proof. The statement would be useful to me, and although I've spent a long time looking at it there's ...
2
votes
5answers
113 views

How to show that $p!+1\equiv 1 \mod k$

I am a non mathematician who is taking a self study class in number theory. I was wondering how to formally prove the following: Let $p$ be a prime number. How can I show that $$p!+1\equiv 1 \mod k$$ ...
3
votes
2answers
72 views

Is $\sum\limits^n_{k=0}\frac{(y-0)(y-1)\cdots(y-n)}{y-k} \equiv 0 \pmod{n+1}$?

Let $n$ be a positive integer such that $n+1$ is a prime power. That is, to illustrate $n+1$ is $9$ or $25$. Prove that $$\sum^n_{k=0}\frac{(y-0)(y-1)\cdots(y-n)}{y-k} \equiv 0 \pmod{n+1}.$$ Hint: I ...
3
votes
6answers
2k views

Arithmetic with Large modular exponent and repeated squaring, such as $10^{221}$ (mod $13$).

How would you compute $10^{221}$ mod $13$ by repeated squaring? I just started studying discrete mathematics and I think this would help me in the future. I looked at this example Computing large ...
1
vote
3answers
230 views

Computing large modular numbers

How do you compute large modular arithmetic such as $8^{128}$ $mod$ $100$ or $10^{111}$ $mod$ $137$ or $3^{100}$ mod $17$? I know that one way is repeated squaring. For the first one, my book says 16, ...
3
votes
2answers
61 views

Modular Exponentiation

Give numbers $x,y,z$ such that $y \equiv z \pmod{5}$ but $x^y \not\equiv x^z \pmod{5}$ I'm just learning modular arithmetic and this questions has me puzzled. Any help with explanation would be ...
3
votes
3answers
235 views

What will be the units digit of $7777^{8888}$?

What will be the units digit of $7777$ raised to the power of $8888$ ? Can someone do the math with explaining the fact "units digit of $7777$ raised to the power of $8888$"?
2
votes
3answers
95 views

Solve for $x$: $4x = 6~(\mod 5)$

Solve for $x$: $4x = 6(mod~5)$ Here is my solution: From the definition of modulus, we can write the above as $ \large\frac{4x-6}{5} = \small k$, where $k$ is the remainder resulting from ...
2
votes
3answers
251 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
2answers
216 views

Miller-Rabin Primality Test

I am trying to work out the potential primality of 341 using the Miller-Rabin algorithm. Below is as far as I get, I'm not really sure where to go from there. I believe I am supposed to use modular ...
1
vote
1answer
76 views

Modular Arithmetic: $ 291-118 \pmod 4\;$?

How do you work out: the value of $ 291-118 \pmod 4\;$? Thanks
4
votes
2answers
124 views

“Tricky” wording on Congruence Modulo Question?

I'm asked for all possible values, but I can only see one. The question on my practice exam reads: Consider the equivalence class [3] for the equivalence relation "congruence modulo $7$" on $\Bbb Z$. ...
1
vote
1answer
28 views

Order of $(F_{k-1}$ mod $p)$ in $F_p^*$ for primefactor $p$ of fermat number $F_k$.

Let $p$ be a primefactor of $F_k = 2^{2^k} + 1$. I proved that $(2$ mod $ p)$ has order $2^{k+1}$ in $F_p^*$. Suppose that $k \geq 2$. How does it follow that $(F_{k-1}$ mod $p)$ has order $2^{k+2}$ ...
1
vote
0answers
92 views

Last 2 digits of modular exponentiation

Is there any shortcut way to find the last two decimal digits of a modular exponentiation (base always is a single digit number) without doing square and multiply? As an example in $$2^{100001} ...
3
votes
5answers
4k views

Finding the last digit in a large exponent.

I'm practicing for my algebra exam but I stumbled on a question I don't know how to solve. Let $N = 3^{729}$. What is the last digit of $N$? The example answer says Since gcd $(3, 10) = 1$, ...
3
votes
1answer
70 views

Find all integer solutions of $35x^{31} + 33x^{25} + 19x^{21} \equiv 1 \pmod{ 55}$

Find set of all integers x for which the following holds: $35x^{31} + 33x^{25} + 19x^{21} \equiv 1 \pmod {55}$ Since $55 = 5\cdot 11$, simultaneous congruences: $35x^{31} + 33x^{25} + 19x^{21} ...
1
vote
2answers
46 views

Simple modular arithmetic question

Can someone please give a clear explanation on how from $(41)(59)x\equiv x\pmod {78}$ and $(41)(59)x\equiv 123\pmod {78}$ we get $x\equiv 123\pmod {78}$?
1
vote
0answers
62 views

A discrete question about modulo

I need conditions for $a, b, c$ such that the system $x \equiv a \pmod{15}$, $x \equiv b \pmod{21}$, $x \equiv c \pmod{35}$ has a unique solution $\pmod{105}$. It must be proved that conditions are ...
1
vote
2answers
117 views

Why is a prime number needed for the Diffie-Hellman key exchange? (modular arithmetic)

I'm writing a cryptography essay, and am wondering why you need a prime number for the deffie-hellman key exchange? Any help would be appreciated :) this is a link to a previous post which quickly ...
3
votes
2answers
183 views

$\mathbb Z_p^*$ is a group.

I'm trying to prove that $\mathbb Z_p^*$ ($p$ prime) is a group using the Fermat's little theorem to show that every element is invertible. Thus using the Fermat's little theorem, for each $a\in ...
2
votes
3answers
91 views

Congruence Problem

Given $a,m \in\mathbb{N}$ with $gcd(a,m)=1$, let $x_1\in\mathbb{N}$ be a solution to the congruence $ax\equiv1\pmod m$. For each integer $k\ge1$, number is defined as $x_k:=\frac{1}{a}(1-(1-ax_1)^k]$. ...
4
votes
1answer
160 views

Using Fermats Little Theorem to show $2^{17} -1$ is prime

Show that $n = 2^{17} - 1$ is prime by using Fermat's Little Theorem $2^{p-1} \equiv 1 \mod p$ for any $p$ dividing $n$. I said, that by FLT, we get $2^{16} \equiv 1 \mod 17$, and we can see that ...
0
votes
1answer
58 views

Number Theory Proof Need Logic Checked

I'm working on the following problem: Show that if $x^{p} + y^{p} = z^{p}$, then $p \space | \space (x + y -z)$ So far my proof looks something like this: Suppose $p \nmid \space (x+y-z)$ ...
0
votes
3answers
87 views

Modulo number multiplied by constant

I am proving that for any integers $a,b$, it is impossible to write $a^2 - 5b^2 \equiv 2 \mod 4$. The first thing I have said is to assume $a,b$ are both even. So I have said $$a,b \equiv 0 \, \, ...
4
votes
6answers
109 views

Prove $7|x^2+y^2$ iff $7|x$ and $7|y$

The question is basically in the title: Prove $7|x^2+y^2$ iff $7|x$ and $7|y$ I get how to do it from $7|x$ and $7|y$ to $7|x^2+y^2$, but not the other way around. Help is appreciated! Thanks.
0
votes
1answer
521 views

How can you find large powers modulo n?

I am following an example in my book as follows: Find 7^64 mod 120. Note: (7,120) = 1 and φ(120) = 32, so 7^64 ≡ 7^0 ≡ 1 mod 120. This part I understand. It's ...
3
votes
1answer
1k views

Prove the converse of Wilson's Theorem

... namely that if $n > 1$ and $(n − 1)!\equiv−1\pmod{n}$, then $n$ is prime. This is for a number theory class I'm in at Penn State. My idea is to follow accordingly, but I can't get it ...
3
votes
3answers
197 views

The Chinese Remainder Theorem

I'm trying to do some questions on the Chinese Remainder Theorem, I've being reading the Wikipedia explanation but I still don't get it. Can someone explain it to me, please? Here is the question I'm ...
6
votes
3answers
151 views

Aut $\mathbb Z_p\simeq \mathbb Z_{p-1}$

I'm trying to prove that Aut $\mathbb Z_p\simeq \mathbb Z_{p-1}$ (p prime). I know that Aut $\mathbb Z_p$ has $p-1$ elements because $\mathbb Z_p$ has $p-1$ possiblities of generators, so intuitively ...
2
votes
0answers
36 views

Is there any relation between the modular inverse of the same integer under different modulus?

I mean, suppose $$ab \equiv 1 \mod{m}$$ $$ac \equiv 1 \mod{n}$$ I wonder if there is any relation between $b$ and $c$? Could we compute one from another? Thanks in advance!
4
votes
3answers
142 views

Show that there exists $f ∈ \mathbb{Z}$ such that $f^2 + f +1 ≡ 0 \pmod p$.

Let $p ≡ 1 \pmod 3$ be a prime. Show that there exists $f \in \mathbb{Z}$ such that $f^2 + f +1 \equiv 0 \pmod p$. I know the first few primes of this form are: $7,13,19$ So for example $p=7$ we ...
0
votes
1answer
70 views

Does $ \ (g^a Mod\ p)^b\, $ $\equiv$ $ \ (g^a)^b (Mod\ p)\, $ hold true?

Are these two equations: $$ \ (g^a Mod\ p)^b\, $$ $$ \ (g^a)^b (Mod\ p)\, $$ one and the same? If yes then how And if no then how to solve the first equation?
4
votes
2answers
94 views

Finding root using Hensel's Lemma

Hensel's Lemma calculates root of a polynomial $\in \mathbb{Z}_p[X]$ but is there any other significance to other branches of mathematics or outside mathematics? Why is finding root of ...
0
votes
2answers
61 views

Trying to prove $A=\{2, 4, 8,…,2^k\}$ is closed under multiplication in $\mathbb{Z}/(2^{k+1}-2)\mathbb{Z}$

I've been investigating as part of a project the structure of integers modulo $n$ ($\mathbb{Z}$/n$\mathbb{Z}$) under multiplication. One aspect I'm looking at is, for any natural number $k$, finding a ...
3
votes
4answers
100 views

Modular Algebra with Powers?

Is it possible to calculate by modular algebra rules (with no calculators) numbers with powers $\textrm{mod}\ n$? Something like: $7^{127} \textrm{mod}\ 11$. If so, how it can be done? Any ...
2
votes
2answers
65 views

Solve the congruence $59x\equiv 3\pmod {78}$

The question is: Solve the congruence $59x\equiv 3\pmod {78}$ So I already found the inverse of $59\pmod{78}$ which is $41$. So $41 \cdot 59\equiv 1\pmod {78}$ The solution is: $59x\equiv 3\pmod ...
2
votes
1answer
76 views

Solve the special congreuences equation?

the following congruencies $\begin{matrix} x_1\equiv1~(\mod m_1)\\ x_2\equiv1~(\mod m_2)\\ \vdots\\ x_n\equiv1~(\mod m_n)\\ \end{matrix}$ where $m_i, m_j(i\neq j)$ are pairwise coprime. Now, I known ...
-1
votes
3answers
143 views

Find the smallest natural number that satisfy $13^N = 1 \pmod {2013}$

Moderator Note: This is a current contest question on Brilliant.org. Find the smallest natural number that satisfy: $$13^N = 1 \pmod {2013}$$ My idea is to use the Fermat's little theorem ...
2
votes
3answers
149 views

Wiki proof of Lucas primality test

I have a question about one step in the proof: Why does $a^{n-1} \equiv 1\ (\operatorname{mod} n)$ imply that $a$ and $n$ are coprime? Thank you!
1
vote
1answer
65 views

Solving for x in a mod relation? [duplicate]

How do I approach the problem: $$7^{95} \equiv x^3\text{(mod 10)}$$ when solving for $x$?
1
vote
3answers
178 views

Congruence Relation with exponents and variables

I am currently trying to solve a congruence relation with a constant and a variable, both of which have attached exponents. The relation is as follows: $7^{95}\equiv x^{3} (mod 10)$ How does one ...
9
votes
1answer
186 views

Elementary Number Theory; prove existence

Prove that there exists a positive integer $n$ such that $$2^{2012}\;|\;n^n+2011.$$ I was wondering if you could prove this somehow with induction (assume that $n$ exists for $2^k|n^n+2011$ ...
0
votes
0answers
54 views

Modulus question [duplicate]

Hey i am studying for my exam and I was wondering how to solve $2023^{2297}\equiv x \pmod{3953}$. The example just says it is $20 \bmod{3953}$ but I am unable to arrive at this answer. Thanks so much ...
1
vote
2answers
150 views

Chinese remainder theorem example help

I am currently studying for my upcoming algebra exam and I was wondering if anybody could explain to me this example of a very basic CRT question. If $x=38$ then $x \equiv 2 \pmod{9}$ and $x ...
9
votes
7answers
3k views

Pattern to last three digits of power of $3$?

I'm wondering if there is a pattern to the last three digits of a a power of $3$? I need to find out the last three digits of $3^{27}$, without a calculator. I've tried to find a pattern but can not ...
1
vote
3answers
142 views

Basic Modulo Question

I've been having trouble with this example while studying for my exams. Why is $$2023^{2297}\equiv 20 \pmod{3953}\;?$$ Thanks so much for any help I can get! The examples solves the answer by ...
1
vote
1answer
60 views

Equivalent modulos

In my course notes I came onto two examples for finding remainders of huge numbers with fermat's little theorem and need some helping analyzing them. 1) Find the remainder when 5^183 is divided by ...
2
votes
4answers
109 views

If $3^x \bmod 7 = 5$, what is $x$ and how?

I am an amateur java programmer who is stuck on this problem: $$3^x \bmod 7 = 5$$ then what is $x$ and how? If you can even explain the method for how to arrive at the solution, then it will be very ...