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
1answer
34 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 ...
2
votes
2answers
54 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 ...
3
votes
1answer
21 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 ...
0
votes
1answer
43 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.
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 ...
0
votes
1answer
27 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
19 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 ...
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}$ ...
1
vote
2answers
11 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}}$$ ...
1
vote
0answers
25 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
70 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
2answers
28 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
54 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
0answers
27 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
24 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
53 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
50 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. ...
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
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 ...
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)$? ...
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.
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 ...
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
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
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.
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} ...
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
48 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$ ...
6
votes
3answers
622 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
30 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
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 ...
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 ...
3
votes
1answer
33 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
45 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 = ...