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
2answers
35 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
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'$ ...
0
votes
1answer
88 views

Equality simplification — have I done it correctly?

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
0answers
30 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
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 ...
0
votes
1answer
26 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 ...
2
votes
3answers
57 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 ...
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 ...
1
vote
2answers
57 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 2+n\overset ...
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. ...
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})$ ...
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 ...
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 ...
1
vote
1answer
23 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 ...
1
vote
0answers
50 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)$? ...
0
votes
5answers
75 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.
2
votes
1answer
56 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 ...
0
votes
2answers
34 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
34 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
0answers
45 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.
0
votes
1answer
27 views

Find the remainder without Fermat's Theorem.

Find the remainder when $27^{3333}$ is divided by 31. So far, I tried rewriting it as $3^{9999} \equiv x\pmod {31}$, and I noted that $gcd (3,31)=1$ but I don't seem to be getting anywhere. All the ...
2
votes
1answer
49 views

Solve $\begin{cases}x\equiv-4\pmod {17}\\ x\equiv 3\pmod{23} \end{cases}$

Solve $$\begin{cases}x\equiv-4\pmod {17}\\ x\equiv 3\pmod{23} \end{cases}$$ My attempt: $$\gcd (17,23)=1$$ so using the Chinese remainder theorem there is a solution modulo $17\times 23=391$ $$x=...
6
votes
3answers
629 views

Find the remainder when a large number is divided by 35.

I don't know why I am wrong with this problem. Here is what I did: The last two digit of $6^{2006}$ is 36. So the answer should be 1. Find the remainder when $6^{2006}$ is divided by 35.
0
votes
0answers
16 views

Number of roots of quadratic polynomial in $ Z/(pq Z) $

I want to prove that quadratic polynomials in $ Z/(pq Z)$ have at most 4 roots, when $ p, q $ are prime. I currently do this by factoring the polynomial, $(x-a)(x-b) $ and then showing that either x ...
1
vote
1answer
37 views

If $ p\neq q$ are odd prime integers then $(\mathbb{Z}/ pq\mathbb{ Z})^*$ is not cyclic

This is a question from Aluffi's Algebra Chapter 0, which I am self studying. Specifically this is from Chapter 2, Page 69, Question 4.10 Let $p\neq q$ be odd prime integers; show that $(\mathbb{Z}/ ...
0
votes
1answer
24 views

Integers that squared have the same last two digits

I need to find the integers that when squared they maintain the las two digits, I've started like this: being b and a the last two digits of the number $(10b+a)²\equiv 10b+a \mod(100) \Rightarrow 20ab ...
2
votes
2answers
50 views

$12^7+8^8$ divided by $13$

I Need to find what the remainder is when $12^7+8^8$ is divided by $13$ I have a solution, but don't know if it is right. $12=-1\mod13$ $12^7=-1\mod13$ $8=8\mod13$ $8^2=6\mod13$ $8^4=10\mod13$ $...
1
vote
3answers
62 views

Show that if $n\equiv 3, 6 \pmod9 $ then $n$ is not a sum of two squares

Show that if $n\equiv 3, 6 \pmod9 $ then $n$ is not a sum of two squares. I started by: Assume $n=a^2+b^2$ a sum of two squares. Then $a^2,b^2\equiv 0,1,4,7 \pmod9$, and no combination these numbers ...
1
vote
2answers
41 views

Elementary Number Theory: Chinese Remainder Theorem

Using the facts that $1591=37.43$ and $51=3.17$ compute 1591 mod 51 using the Chinese Remainder Theorem. I started off by letting $x \equiv 1591 \mod 51$ which I then wrote as $x \equiv 1591 \mod 17$...
0
votes
1answer
57 views

Prove that $n^2+11n+2$ is not divisible by $12769$ [duplicate]

My Attempt : Prime factorisation of $12769$ is $113^2$ $n^2+11n+2-113^2m=0$ The conjugate of this quadratic equation becomes: $\sqrt {113 (113m+1)} $ which can never be a rational as (113,113m+1)...
3
votes
1answer
38 views

Prove that for every polynomial $x^n$, $x^n(mod(x^4 + 1)) = x^{n(mod4)}$

I am trying to prove the following: Assuming $GF(2^k)[x]$ (where $k$ is a fixed natural number) is a ring of polynomials with coefficients in the field $GF(2^k)$. Prove that for every polynomial $x^n$...
0
votes
1answer
27 views

$x^{(p-1)/d}$ takes d distinct values

Im working on this Exercise I can do do part b) but Im stuck on part c). I know that if $e$ is a positive factor of $p-1$ then the equation: $$X^e \equiv 1 \quad \textrm{mod p} $$ has exactly $e$ ...
0
votes
1answer
41 views

$\gcd(a, 63) = 1$ implies $a^7 \equiv a \mod 63$?

Let $a$ be an integer. Suppose that $\gcd(a,63) = 1$. Prove then that $$a^7 \equiv a \mod 63. $$ Attempt: Since $gcd(a,63) = 1$, by Fermat little theorem we have that $$a^{\phi(63)} \equiv 1 \mod 63....
1
vote
1answer
53 views

solve pairs of two variable simultaneous linear modular equations

I’m looking for a method to solve pairs of simultaneous linear modular equations, such as 323x + 37y = 0 Mod 243; -397x + 683y = 0 Mod 32 I’ve simplified this to 80x+37y = 243g; 19x+11y = ...
0
votes
0answers
25 views

find residue modulo

Find the residue , modulo $317$, of $5^{17}$. Hence calculate the residue, modulo $317$ of $401 (5^{17})$. Really struggling with this question I have attempted the first part as follows \begin{align}...
1
vote
1answer
49 views

Solve $276 x\equiv 90\pmod {666}$

Solve $276 x\equiv 90\pmod {666}$ I found using Euclidean algorithm that $\gcd (276,666)=6$ then I divided by $6$ and I got: $$46x\equiv 15\pmod {111}$$ and I found that $\gcd(46,111)=1$ using ...
-3
votes
1answer
77 views

Prove that there are infinitely many values of $n$ for which $\phi(n)=\frac{n}{2}-1$

I know that $\phi(n)=\frac{n}{2}-1$ is actually one of the strong lines on a plot of Euler's phi function, the other being $\phi(n)=n-1$. However I don't know how to go about proving it. Where should ...
1
vote
0answers
12 views

Let $S$ be a set. For each $i\in\mathbb{N}\cup\{0\}$ let $E_i$ the free module over $\mathbb{Z}$ generated by S^{i+1}$. Define…

I need some help with this problem, I really don't undertand how to start, thanks. Let $S$ be a set. For each $i\in\mathbb{N}\cup\{0\}$ let $E_i$ the free module over $\mathbb{Z}$ generated by the ...
3
votes
1answer
35 views

Show that $\xi^3\equiv \pm 1 \pmod{\lambda^4}$ in $\Bbb Z [\omega]$

We have $\lambda=1-\omega$ where $\omega=e^{i 2\pi/3}$ and $\xi$ an Eisenstein integer. Given that $\xi \equiv \pm 1 \pmod{\lambda}$, how can I prove that $$\xi^3\equiv \pm 1 \pmod{\lambda^4}$$ I ...
-1
votes
1answer
26 views

If $\gcd(k, p-1) = 1$ show that $x^k \equiv l \pmod{p}$ has at most one solution.

Assume that $k$ is a natural number and $p$ is a prime where $\gcd(k, p-1) = 1$ Let $l$ be an integer show that $x^k \equiv l \pmod{p}$ has at most one solution. I'm pretty sure I have to somehow use ...
0
votes
0answers
22 views

Mod devision - there are two different solutions

This is my working The question asks us to find the solution in the form of x = k (mod 65). But I also found a solution in the form of mod (13), but they are totally different. Which one is correct? ...
3
votes
2answers
68 views

Show that the cube of any integer is congruent to $0$ or $\pm 1 \pmod 7 $

For any integer, $n$, show that $n^3 \equiv 0$ or $\pm 1(\mod 7)$. Use theory of congruences So I thought about a couple of ways to go with this. I thought about showing $7|n^3$ or $7|n^3\pm1$ to be ...
1
vote
4answers
81 views

A positive integer (in decimal notation) is divisible by 11 $ \iff $ …

(I am aware there are similar questions on the forum) What is the Question? A positive integer (in decimal notation) is divisible by $11$ if and only if the difference of the sum of the digits in ...
0
votes
2answers
49 views

Let G be a group with identity $e$. If $a,b$ are integers, and $x$ is an element in G such that $x^a=e$ and $x^b=e$, then show that $x^{gcd(a,b)}=e$

I'm not really sure how to start this proof. Should I start with 3 different cases, $a=b, a<b, a>b$? If $a=b$, then of course $gcd(a,b)=a=b$ and so $x^{gcd(a,b)}=x^a=x^b=e.$ If $a<b$, ...
0
votes
0answers
49 views

Suppose that n=ab, where a ≥ b > 2 and gcd (a,b)=1. By working mod a and mod b, prove that there are at least 4 different solutions to x^2.=1 mod n.

I've started by stating that if $x^2=1\mod n$, since $n=ab$ and $gcd(a,b)=1$, then $x^2=1\mod a$ and $x^2=1\mod b$. Now, I know that for $a,b \gt 2$, there will always be at least two solutions for $...
0
votes
1answer
12 views

Find all Dirichlet characters modulo $p$

In my elementary number theory class we define the following: Let $p$ be a prime, and let $\mathbb{Z}_p^*$ relatively prime residues modulo $p$. A Dirichlet character modulo $p$ is defined as a ...
1
vote
3answers
32 views

Find the remainder of $\sum_{i=0}^{99} 2^{i^2}$ when dividing by 7 and determine if the quotient is even or odd

I've recently had this problem in an exam and couldn't solve it. Find the remainder of the following sum when dividing by 7 and determine if the quotient is even or odd: $$\sum_{i=0}^{99} 2^{i^2}$$ ...
2
votes
2answers
22 views

A question on “law of congruence of modulus”

I have a quick question about the law of congruence of modulus, which states "Let $a•b≡a•c \,(\mod m)$, where $a$ is not equivalent to $0$,$ \mod m$. We can cancel $a$ only when $a$ and $m$ are ...
2
votes
3answers
52 views

Remainder of $2^{100} (\mod\ 89)$

I am having trouble coming to the answer on this question: Find the remainder when $2^{100}$ is divided by $89$. (Hint: Simplify $2^{10} \pmod{89}$ first.) So I went with the hint and found $2^{10} =...