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

0
votes
0answers
32 views

On Modular exponents.

If $g^z=h\bmod p$ where $z$ is the only unknown then is it possible to find in polynomial time $g^{z^t}\bmod p$ at some $t\neq 0$ or $1\bmod(p-1)$?
2
votes
2answers
29 views

Evaluating the remainder of $652^{679} : 851$

Evaluating the remainder of $652^{679} : 851$ I'm having trouble solving this problem, specially because I saw congruence properties a long time ago, but this is what I tried: ...
2
votes
1answer
55 views

Why is any number to the 1,5,9,13, etc. modulus 10 itself?

Why is $n^{4k+1} \% 10 = n$ for any integer $n$ and any whole number $k$? What about base 10 math makes this so?
0
votes
2answers
18 views

prove $a \equiv b \pmod{p_1}$ and $a \equiv b \pmod{p_2} \Rightarrow a \equiv b \pmod{p_1\times p_2}$

I am following a proof of an RSA algorithm and the proof states the following: $p_1$ and $p_2$ are distinct primes, $a \equiv b \pmod{p_1}$ and $a \equiv b \pmod{p_2} \Rightarrow a \equiv b ...
1
vote
2answers
26 views

Find a positive integer $x$ such that $0<x\leq38$ and $14^{36}\equiv x\pmod{38}$

Find a positive integer $x$ such that $0<x\leq38$ and $$14^{36}\equiv x\pmod{38}$$ This is what I've come up with so far: $$14^{36}\equiv x\pmod{38} \iff 14^{36}\equiv x\pmod{19} \, \land ...
7
votes
2answers
446 views

How to solve congruence $x^y = a \pmod p$?

I'm having trouble solving this congruence: $$x^{114} \equiv 13 \pmod {29}.$$ I thought that it made sense to try to solve it using this idea: "Suppose you want to solve the congruence $ x^y \equiv a ...
1
vote
2answers
653 views

How to calculate the mod value of a rational/irrational value?

We have a course in network security this semester and we are being taught RSA algorithm. I came across a typical math problem that I was unable to solve here. $$D*E \equiv 1 \mod{\phi(n)}$$ This ...
4
votes
4answers
85 views

Find the last two digits of $2^{2156789}$

Find the last two digits of $2^{2156789}$. My try: As $2156789 = 4* 539197 + 1$ The unit digit of $2^{2156789}$ is similar to the unit digit of $2^{4n+1}$ which is equal to 2. But I'm unable to find ...
1
vote
1answer
37 views

Find all integers $0\leq x<19$ such that $x^{19}+x^{38}\equiv 2\pmod{19}$

Find all integers $0\leq x<19$ such that $$x^{19}+x^{38}\equiv 2\pmod{19}$$ I think I'm supposed to use Fermat's Little Theorem here and I'm aware that this says that if $p$ is a prime and $a$ is ...
1
vote
1answer
624 views

Solving a non-linear congruence

How can we solve for $x$, knowing the integer $n$ and the real numbers $a$ and $b$, the following non-linear congruence: $(x+a)^2=-b\pmod{n}$ Specifically in this example: ...
0
votes
1answer
46 views

Does $x^2+1$ have roots in $Z_{103}[x]$? [duplicate]

I am trying to figure out if $x^2+1$ has any roots in $Z_{103}[x]$, but I don't have any idea of how I should find the answer. Any help would be much appreciated. Thank you.
3
votes
1answer
23 views

basic modulus question

So if so $a \equiv b \pmod{n}$, which should be read as "$a$ is congruent to $b$ modulo $n$" which from what I understand is something among the lines of "$a$ is the remainder when $b$ is divided by ...
1
vote
1answer
30 views

Find two natural numbers $m$ and $n$ such that the order of $n$ modulu $m$ equal to $2012$

Find two natural numbers $m$ and $n$ such that $\gamma_m(n)=2012$ My atempt: $$\varphi(n)\mid2012$$ $$\Longrightarrow \varphi(n)\in\{1,2,4,503,1006,2012\}$$ I am stuck here
0
votes
0answers
15 views

Solving $ b^k= a~ mod~ 2^n$

I wonder how given $a \in \mathbb{Z}$, $ k,n \in \mathbb{Z}_{\ge1}~ k~odd$, $~~ b^k= a~ mod~ 2^n$ is solvable using Newton-Iteration. I tought of using $X^k-a$ as $f(x)$ and using a validation Ring. ...
0
votes
1answer
12 views

Carry of multiplication in base k

I'm trying to implement a library of big numbers and I'm stuck with multiplication. The issue is not in finding a good algorithm (Karastuba will be fine), but in a way to compute carry of two numbers ...
3
votes
2answers
37 views

The order of $33\pmod{83}$

Find $\gamma_{83}(33)$ My attempt: stupid approach: $33^1\equiv 33 \pmod{83}$ $33^2\equiv 10 \pmod{83}$ $33^3\equiv 81 \pmod{83}$ $33^4\equiv 17 \pmod{83}$ $33^5\equiv 63 \pmod{83}$ ...
0
votes
1answer
28 views

Find Integer Solution for $(g^x) \bmod p = 1$

Consider the following: $(g^x) \bmod p = 1$, where $p$ is a prime; $g$ is a primitive root modulo $p$. Is it possible to find the integer solution for any $p$, $g$?
1
vote
1answer
20 views

Relation between powers of inverse modulo n.

Recently, I was studying enchanced euclidean algorithm. I am wondering if there is some way to calculate inverse of $a^2$ (and higher powers) modulo $n$, knowing inverse of $a$ modulo $n$. For ...
1
vote
2answers
12 views

the connection between $\gamma_m(a)$ and $\gamma_m(b)$ when $a\cdot b\equiv 1\pmod m$

show the connection between the order of $a$ $\gamma_m(a)$ and the order of $b$ $\gamma_m(b)$ when $$a\cdot b\equiv 1\pmod m$$ I took $a=5$ and $b=4$ $$5\cdot 4\equiv 1\pmod{19}$$ ...
1
vote
3answers
53 views

Solve $636^{369}\equiv x\pmod{126}$

Solve $$636^{369}\equiv x\pmod{126}$$ My attempt: $$126=2\times 3^2 \times 7$$ $$\varphi(126)=\varphi(2)\times \varphi(3^2)\times \varphi(7)=36$$ $$\color{gray}{636=6\pmod{126}}$$ ...
0
votes
1answer
32 views

On exponent mod $2p$.

Assume $p$ is a prime. Assume $g$ is primitive root for both $\Bbb Z_p$ and $\Bbb Z_{2p}$. We know in discrete logarithm problem $z$ is unique $\bmod(p-1)$ in $g^z=h\bmod p$. Is it true that $z'$ ...
1
vote
0answers
26 views

Calculate modulo expression

How does one evaluate the expression; $$5\times52^{366} \mod367^1$$ I can infer from the exercise solutions that $52^{366} ≡ 1 \mod 367$, but why?
1
vote
2answers
71 views

How to find remainder of a very large number when divisor is 17?

How to find the remainder when $2^{2015}$ is divided by $17$? I tried dividing $2,4,8,16$ etc by $17$ and finding the remainder in each case to form some particular sequence but failed can someone ...
0
votes
0answers
29 views

Prove: $\bar{a}^2 = \bar{0}$ in $\mathbb{Z}_{pq} \rightarrow \bar{a}=0$ where $p\neq q$ are primes

For this summer, I am teaching myself abstract algebra and I've been working on a proof for the following statement. I just need someone to confirm whether it is sound. (Note: Here, $\bar{a}$ denotes ...
0
votes
2answers
29 views

Application of Fermat's Little Theorem/Fermat Euler Theorem

Find an integer $x$ with $0\leq x \leq73$ such that $$2^{75}\equiv x \pmod{74}$$ I think I'm supposed to be using either Fermat's Little Theorem or the Fermat-Euler theorem here but I don't think I ...
0
votes
1answer
57 views

Another gnarly equality.

I previously posted this equality and got some nice feedback. This is my final equality to prove Legendre's, Brocard's, Andrica's, and Oppermann's Conjectures. The first equality was to determine if ...
0
votes
1answer
29 views

Systems of linear equations in the same modulus

I am working with a system of linear equations all taken with the same modulus, $n$, there is no assumption on $n$ other then it is at least 3 (really don't want to assume it is prime) I don't have ...
0
votes
1answer
27 views

Modulo Arithmetic - Chinese Remainder Theorem

Solve the linear congurence $17x\equiv 3(\mod{2*3*5*7})$ by solving the system: $17x\equiv 3(\mod{2})$ For this one, I simplified to $x\equiv 1(\mod{2})$. Let this $x=5$. $17x\equiv 3(\mod{3})$ ...
0
votes
1answer
25 views

How many complexes modulo a prime $p$ are of multiplicative order $p^2 - 1$?

If $i = \sqrt{(-1)} \bmod p$, $p$ prime, does not exist, then we can form numbers of the form $a+b i \bmod p$ with multiplicative order $p^2 - 1$. How often do these numbers occur modulo $p$? In ...
0
votes
0answers
17 views

Calculating modulus by coprimes

I need to calculate $x$, which is defined as the unique integer in $\{0,1,...,(pq - 1)\}$ such that $x \equiv n\mod{pq}$, where $n > 0$, $p$ and $q$ are relatively primes ($n, p, q$ are known ...
2
votes
3answers
55 views

How quickly can we detect if $\sqrt{(-1)}$ exists modulo a prime $p$?

How quickly can we detect if $\sqrt{(-1)}$ exists modulo a prime $p$? In other words, how quickly can we determine if a natural, $n$ exists where $n^2 \equiv -1 \bmod p$? NOTE This $n$ is ...
0
votes
1answer
18 views

Proving the element of a symmetry group $\sigma^i \in S_n$ is of order $n$ and length $n$ only when $(n,i) = 1$

Start with element of $S_n$ as $\sigma^i$ which permutes an element of the set $\{1,2,3,...,n\}$, call it, $a_k \to a_{k+i}$ So $({\sigma^i})^2$ would permute $a_k \to a_{k+2i}$ If $k+i > n$, the ...
1
vote
2answers
51 views

Prove that the last digit of $4n^5-5n^2+n$ is $0$

Prove that the last digit of $4n^5-5n^2+n$ is $0$ for all natural $n$ My attempt: $$4n^5-5n^2+n\overset{?}\equiv 0\pmod {10}$$ using Fermat's little theorem $$4n\cdot\pmod 5 -5n\pmod ...
0
votes
0answers
6 views

On volume of arithmetic subgroups

I deal a lot with volumes of arithmetic subgroups, mainly in $SL_2(\mathbf{Z)}$. But I remain not at ease with them, making rough explicit calculations case by case instead of having a general method. ...
1
vote
1answer
37 views

How to split congruences so moduli are prime powers?

If I have the linear congruence x=5 mod 84, is this equal to x=2 mod 3, since 3|84? This seems too easy.
1
vote
1answer
22 views

Prove that for integers $a$, $b$, and $n$, if $a$ and $b$ are each relatively prime to $n$, then the product $ab$ is also relatively prime to $n$.

Please help! I need a proof using modulars on proving that with integers $a$, $b$, and $n$, if $a$ and $b$ are each relatively prime to $n$ then the product $ab$ is also relatively prime to $n$. So ...
3
votes
3answers
3k views

Find modulo of multiplication of two number?

Given $m$, $a$ and $b$ are very big numbers, how do you calculate $ (a*b)\pmod m$ ? As they are very big number I can not calculate $(a*b)$ directly. So I need another method.
1
vote
3answers
24 views

Will the remainder of multiple dice rolls be fair if at least one roll is performed fairly?

Suppose Alice and Bob are playing a dice game. They each hold a six sided die and a cup. They shake their die in the cup, flip the cup on the table and reveal the roll at the same time. The result is ...
0
votes
3answers
85 views

proving for all odd integers that $n^2 + 2n \equiv 0 \pmod{3}$

prove that for all odd integers, $3 |(n^2 + 2n)$ An even integer may be described as $2k$ and an odd one as $(2k+1)$, inserting it in to our equation gives us $(2k+1)^2 + 2(2k+1) $ $=4k^2 + 8k + 3$ ...
1
vote
5answers
71 views

Prove that if $n$ is not divisible by $3$, then $n^2 \equiv 1 \pmod 3$

I can see that it is true for all cases where $n$ is not divisible by $3$, such as $n = 1$, $n = 2$, $n = 4$, etc. However I can't figure out how to prove it.
1
vote
1answer
32 views

identity on Pascal's triangle modulo 2

Consider Pascal's triangle with entries modulo $2$, and let $(k,l)$ denote the $l$-th entry in the $k$-th row by $(k,l)$. Show that, for all $n \in \mathbb{N}$, each entry of the triangle with ...
2
votes
2answers
137 views

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

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$ ?
1
vote
0answers
47 views

When is a prime $p$ a quadratic residue modulo $3$?

Simple. When $p \equiv 1 \pmod 3$, it is a quadratic residue, and when $p \equiv -1 \pmod 3$ it is not a residue. So can we have a nice expression for the Legendre symbol $\left(\frac{p}{3}\right)$? ...
2
votes
1answer
54 views

Solve $\begin{cases}x\equiv 1\pmod{5}\\x\equiv0\pmod{66}\\x\equiv6\pmod 7\end{cases}$

Solve $$\begin{cases} x\equiv 1\pmod{5}\,\,\,\qquad\qquad.1\\ x\equiv0\pmod{66}\qquad\qquad.2\\ x\equiv6\pmod 7\,\,\,\qquad\qquad.3 \end{cases}$$ My attempt: $\gcd(66,5,7)=1$ so I can apply the ...
1
vote
3answers
98 views

Show that for any odd $n$ it follows that $n^2 \equiv 1 \mod 8$ and for uneven primes $p\neq 3$ we have $p^2 \equiv 1\mod 24$.

Show that for any odd $n$ it follows that $n^2 \equiv 1 \mod 8$ and for uneven primes $p\neq 3$ we have $p^2 \equiv 1\mod 24$. My workings so far: I proceeded by induction. Obviously $1^2 \equiv 1 ...
0
votes
0answers
33 views

Relating discrete logs with two different modulus.

Assume $p$ is a prime. Assume $g$ is primitive root for both $\Bbb Z_p$ and $\Bbb Z_{2p}$. We know in discrete logarithm problem $z$ is unique mod $p-1$ in $g^z=h\bmod p$. Then we know that $g^z=h ...
0
votes
2answers
28 views

RSA Public key-Prove that if any one of p,q,ϕ(n) is known, then you can quickly use it to find the other two as well.

I'm a little confused as to how to go about this, I've read through the bottom answer to this question : RSA solving for $p$ and $q$ knowing $\phi(pq)$ and $n$ but in that question they find p and q ...
0
votes
0answers
44 views

Do the odd numbers modulo $2^n$ form a field?

Do the odd numbers modulo $2^n$ form a field (of order $2^{n-1}$) for some $n$? For $n$ a power of 2? If so, this would be quite useful for cryptography.
1
vote
0answers
42 views

Notation error in modular arithmetic problem

My calculus teacher recently gave us a problem concerning number theory. It was to find the error in $$ 10\equiv 3\pmod 7 $$ Apparently the error is the notation - there is a way to rewrite this ...
0
votes
0answers
14 views

First digit inequality [closed]

If $d_n$ is the first digit of $n$ and $f(k)$ is the number of squares $(n+1)^2$ and $n^2$ of $k+1$ digits that hold $d_{(n+1)^2}-d_{n^2}\le1$, then find the sum of the digits of $\sum_{k=1}^{1008} ...