Modular arithmetic (clock arithmetic) is a system of arithmetic of integers. The basic ingredient is the congruence relation $a \equiv b \bmod n$ which means that $n$ divides $b-a$. In modular arithmetic one can add, subtract, multiply and exponentiate but not divide in general. The Euclidean ...
1
vote
0answers
12 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
87 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
32 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?
3
votes
2answers
32 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
30 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
35 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
29 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
53 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
vote
2answers
49 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
60 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
29 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$?
0
votes
0answers
33 views
Monic polynomial
If $f(x)=0 \pmod N$ is monic, how we can prove that $f(x)$ is invertible?
And how about relation multiply $f(x)$ with its inverse when $f(x)$ is not monic?
Anyone can help me to prove this problem? ...
1
vote
3answers
30 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 ...
10
votes
1answer
136 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
40 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 ...
