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
1answer
27 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
21 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
64 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
21 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
25 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
48 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
28 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
22 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
52 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
17 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
46 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
136 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
46 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
53 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
32 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
26 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
43 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} ...
6
votes
3answers
621 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
1answer
25 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
47 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$ ...
2
votes
3answers
76 views

Is it true that a cycle with a period of 29 hours over 24 hours leads to a non-recurring pattern and how to prove it?

The default 'reset time' for Internet Information Services is 29 hours. The reason for this is that 'Wade [person on the team who developed the setting] suggested 29 hours for the simple reason ...
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
29 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}/ ...
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 ...
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
2answers
40 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 ...
2
votes
3answers
99 views

Modulo Inverse using extended euclidean

My aim here to learn the Chinese Remainder theorem. But am stuck at finding the inverses. Suppose we have 42 mod 5, but according to the CRT question, we must make it 42 * x congruent to 1 (mod 5) ...
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 ...
44
votes
2answers
791 views

Fractals using just modulo operation

Let us calculate the remainder after division of $27$ by $10$. $27 \equiv 7 \pmod{10}$ We have $7$. So let's calculate the remainder after divison of $27$ by $7$. $ 27 \equiv 6 \pmod{7}$ Ok, so ...
3
votes
1answer
62 views

Last digit of $1234 \cdot 5678$

How to find the last digit of this multiplication $1234\times5678$. It may seem like homework but its not. I can do simple multiplication to get the result but I see some patter here, the digits are ...
0
votes
1answer
408 views

Calculating nCr mod M using inverse multiplicative factors

The method used for calculating nCr mod M is: fact[n] = n * fact[n-1] % M ifact[n] = modular_inverse(n) * ifact[n-1] % M And then nCr is calculated as ...
3
votes
1answer
31 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 ...
0
votes
1answer
26 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
38 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 ...
1
vote
1answer
44 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 = ...
-3
votes
0answers
41 views

Suppose that $n>1$ & $n$ is not prime power. Prove that $n=ab$ where $a>b>1$ and $gcd(a,b)=1$. [closed]

Suppose that $n > 1$ and n is not a prime power. Prove that $n = ab$ where $a > b > 1$ and $\gcd(a, b) = 1$. By working $\bmod a$ and $\bmod b$, prove that there are at least 3 different ...