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
17 views

The map $\left(\frac{.}{p}\right):=\mathbb F_p \rightarrow [\pm1]$ taking $a\in \mathbb F_p$ to $\left(\frac{a}{p}\right)$ is homomorphism

Prove that the map $\left(\frac{.}{p}\right):=\mathbb F_p \rightarrow [\pm1]$ taking $a\in \mathbb F_p$ to $\left(\frac{a}{p}\right)$ is a homomorphism I don't know how to even start this ...
0
votes
0answers
23 views

Repeated squaring vs. regular modular exponentiation

I initially thought I would use repeated squaring for computations of the for $a^b \ mod \ c$ for large values of $a$ and $c$. Is there a better way to decide?
2
votes
2answers
55 views

Use congruences to factor $n=87463$ (Fermat's Factorization?)

I'm studying for my number theory test tomorrow, and these are the last questions in my study guide. I think I understand Fermat's factorization, however, I can't tell how my professor wants us to ...
2
votes
2answers
22 views

Given $p,q$ odd primes, prove that if $\gcd(a,pq)=1$ then $a^{lcm (p-1,q-1)} \equiv 1 \pmod {pq}$

Given $p,q$ odd primes, prove that if $\gcd(a,pq)=1$ then $a^{\operatorname{lcm} (p-1,q-1)} \equiv 1 \pmod {pq}$ What I am thinking: I know by Fermat's that $a^{p-1} \equiv 1 \pmod p$ and also ...
1
vote
0answers
29 views

Chinese Remainder theorem clarification needed

I'm trying to solve $p\equiv a\pmod{7}$ and $p\equiv b\pmod{4}$ $m_1=(4)^{-1} \pmod 7$ $m_2=(7)^{-1} \pmod 4$ I need to find $m_1'$ and $m_2'$ which I assumed to be the inverse of $m_1$ and ...
0
votes
1answer
18 views

If $p>3$ and $x^2+3y^2=p$, prove $\left(\frac{-3}{p}\right)=1$ and $p\equiv 1\pmod{6}$.

If $p>3$ and $x^2+3y^2=p$, prove $\left(\frac{-3}{p}\right)=1$ and $p\equiv 1\pmod{6}$. $$\left(\frac{-3}{p}\right)=\left(\frac{-1}{p}\right)\left(\frac{3}{p}\right)$$ We know that ...
3
votes
3answers
72 views

Computing $7$th root of $2$ modulo $33$

$\varphi(33) = 20$ $ed = 1 \pmod {20}$, and $d$ is $7$, so $e$ is $3$. $(3 \times 7 \mod 20 \equiv 1)$ So $x^e \pmod {33}$ is the seventh root. But how do you compute $x$? Later: My error was ...
0
votes
2answers
74 views

Why there are more than 2 solutions for $x^{14} = 1$ in $\mathbb{Z}_{113}$?

How to show that the equation $x^{14}=1$ has more than 2 solutions in the field $\mathbb{Z}_{113}$? This is the same as solving $x^{14} \equiv 1 \pmod {113}$. I know that $x^{112} \equiv 1 \pmod ...
0
votes
1answer
32 views

Prove that $x$ and $y$ are divisible by $3$ when $x^2+6u^2=2y^2+3v^2$

a) Solve $x^2\equiv 2y^2\pmod{3}$ b) Use part a to prove that $x$ and $y$ are divisible by $3$ when $x^2+6u^2=2y^2+3v^2$ My attempt: $x^2\equiv 2y^2\pmod{3}\iff $$(y^{-1}x)^2 \equiv ...
7
votes
2answers
123 views

Prove that if $7^n-3^n$ is divisible by $n>1$, then $n$ must be even.

I tried using factorization of $a^n-b^n$ for odd $n$ in an attempt to work through to a situation where the factors are such that they cannot have n as a factor. But I reached nowhere. Here's how I ...
0
votes
2answers
28 views

$x^a\equiv 1\pmod{p} \Rightarrow x \equiv 1\pmod{p}$

We know: $\gcd(a,\phi(n)=1$ and $a,n,x>0$. Show that $\gcd(x,n)=1$ and $x^a\equiv 1\pmod{p} \Rightarrow x \equiv 1\pmod{p}$ My Attempt: Using Euler's Theorem I know that: $x^{\phi(n)}\equiv ...
3
votes
2answers
518 views

Does the element $x^2$ have an inverse in the ring $\mathbb{Z}_2[x]/(x^3-x^2-x+1)$?

In the ring $R = \mathbb{Z}_2[x]/(x^3-x^2-x+1)$, does the element $x^2$ have an inverse? How do I answer such a question? I know how to compute the inverse if it exists, and using the same method in ...
2
votes
2answers
48 views

Suppose $n|a^2-1$ Show that $n=$gcd$(a-1,n)$gcd$(a+1,n)$

Suppose $n|a^2-1$ where $a>1$ and n is odd. Show that $n=$gcd$(a-1,n)$gcd$(a+1,n)$. Part 2 Show that if $a<n-1$ then this gives a nontrivial factorization of n What I did: I found the ...
1
vote
1answer
29 views

System of congruences with polynomials

How do I go about solving exercises such as this one: Find all polynomials $f(x)$ in $\mathbb{Z}_3$ that satisfy $$f(x) \equiv 1 \space \space \mathrm{mod} \space \space x^2 + 1$$ $$f(x) \equiv x ...
1
vote
1answer
30 views

Suppose $(a+i)^{a+i}\equiv a^a \mod p$ for all $a=1,2,..$ Then $i$ is divisible by $p(p-1)$

Suppose $(a+i)^{a+i}\equiv a^a \mod p$ for all $a=1,2,\dots$ Then $i$ is divisible by $p(p-1)$. Solution: Take $a=p$ then we see that $(i+p)^{p+i}\equiv p^p \equiv 0 \mod p$ Since $i+p\equiv 0 ...
0
votes
2answers
29 views

Why is “if $\left(\frac{5}{p}\right)=\left(\frac{p}{5}\right)=1\Rightarrow p\equiv 1\pmod{5}$ or $p\equiv 4\pmod{5}$” true?

Why are the following statements true? $\left(\frac{5}{p}\right)=\left(\frac{p}{5}\right)=1\Rightarrow p\equiv 1\pmod{5}$ or $p\equiv 4\pmod{5}$ ...
0
votes
1answer
28 views
1
vote
1answer
63 views

Maximum remainder $(a-1)^n+(a+1)^n\mod a^2$ for $3\le a\le 1000$

Here's the problem: Let $r$ be the remainder when $(a−1)^n + (a+1)^n$ is divided by $a^2$. For example, if $a = 7$ and $n = 3$, then $r = 42$ since $63 + 83 = 728 \equiv 42 \pmod{49}$. And as ...
3
votes
3answers
73 views

Solve $x^2\equiv -3\pmod {13}$

Question 1) Solve $$x^2\equiv -3\pmod {13}$$ I see that $x^2+3=n13$. I don't really know what to do? Any hints? The solution should be $$x\equiv \pm 6 \pmod {13}$$ Question 2) Given $x\equiv \pm 6 ...
1
vote
0answers
30 views

Need help understanding the solution of: Show that there is no perfect square whose last three digits are 341.

Show that there is no perfect square whose last three digits are 341. Solution: Let x be any integer. Note that if $x^2$ ended with the digits 341, then we would have $$x^2 = 1000k+341$$ for some ...
1
vote
0answers
6 views

Equivalence Clasess modulo n to and exponential

I know that for an equivalence class $$[a]^{[b]_{\phi(m)}}$$ to be well defined, be must be an equivalence class of $\phi(m)$. However, can we always assume that $$[a]^{[b+c]}= ...
0
votes
1answer
26 views

nth root of unity in a cyclic group $\mathbb{Z}_p^*$

Is there a specific set of steps that should be taken in order to the $n$-th root of unity in a cyclic group. To be more specific, I am trying to find the $8$th root of unity for $\mathbb{Z}_{17}^*$. ...
0
votes
1answer
17 views

a ≡ b mod p implies that $(\frac {a}{p}) =(\frac {b}{p})$ The Legendre Symbol

Prove $$a\equiv b\pmod p \Rightarrow (\frac {a}{p}) =(\frac {b}{p})$$ What I thought: Let $g$ be a primitive root mod $p$. Then $(\frac {g^k}{p})=(-1)^k$. What should I do next?
0
votes
0answers
8 views

$\mathbb{Z_p}(x^p,y^p,x-y^n) \neq \mathbb{Z_p}(x^p,y^p,x-y^m)$ for $n \neq m$

I am trying to find an easy proof for the following result: Let $p$ be a prime number. Show that for $n \not\equiv m \mod p$ $$\mathbb{Z_p}(x^p,y^p,x-y^n) \neq \mathbb{Z_p}(x^p,y^p,x-y^m).$$ The ...
2
votes
5answers
105 views

True or false: There is no square $6$ mod $7$.

True or false: There is no square $6$ mod $7$. If you find an example, then you are finish. If you cannot find an example, then prove that the below statement is not true. $$ x^2 \equiv 6\mod 7$$ ...
0
votes
1answer
28 views

simple RSA decypher

I think my confusion here is just which how the question was given to me. I am having trouble decrypting this simple RSA message. Message: $0882~ 1090~ 1471~ 1899~ 2753~ 0309$ $p = 43 ; q = 71; e = ...
0
votes
2answers
33 views

For which $x$ is $2^{x+1}-2 \equiv 0 \pmod{29} \quad and \quad 2^{x+1}-4 \equiv 0 \pmod{28}$

In $$2^{x+1}-2 \equiv 0 \pmod{29} \quad and \quad 2^{x+1}-4 \equiv 0 \pmod{28}$$ How can I find for which $x$ this holds true. $x$ is a positive integer
2
votes
1answer
40 views

Roots of $x^2+1$ over $\mathbb{Z}_7$?

Prove that $x^2 + 1$ is irreducible in the ring of polynomials $\Bbb Z _7 [x]$ over the field $\Bbb Z _7$. Is it enough to show that no single element of $\mathbb{Z}_7$ squared is equal to $-1 \pmod ...
0
votes
1answer
40 views

Why (Zn,*), integers modulo n under multiplication, is a group if and only if n is prime? is a group if and only if n is prime?

Is it true that $(\Bbb Z_n,\cdot)$, integers modulo $n$ under multiplication, is a group if and only if $n$ is prime? If it's true, why? How can I prove it?
0
votes
1answer
25 views

How to find the solutions $x \in \mathbb{Z}$ such that $13x \equiv 1$ mod $15$ and $ x^2 \equiv 9$ mod $100$.

I calculated that the first equation is equal to $x \equiv 7$ mod $15$. When solving $x^2 \equiv 9$ mod $100$, i found $x \equiv \pm 3$ mod $100$ and $x\equiv \pm 47$ mod $100$. But since the CRT ...
0
votes
1answer
26 views

(1234)%6 = ((123%6)*10 + 4)%6 why this relation works?

I know these relations, (a * b * c * d...)%m = ((a%m) * (b%m) * (c%m) * (d%m)......) %m and (a+b+c+d+........)%m = (a%m + b%m + c%m + d%m)%m But , how does this relation work? 1297 % 6 = ...
2
votes
2answers
62 views

True or false: If $x^2 \equiv 14 \pmod{15}$ then there exists an $x^2$ that makes this congruent

True or false: If $x^2 \equiv 14 \pmod{15}$ then there exists an $x^2$ that makes this congruent $0^2\equiv0 \mod 15$ $1^2\equiv1 \mod 15$ $2^2\equiv4 \mod 15$ $3^2\equiv9 \mod 15 $ $4^2\equiv1 ...
0
votes
1answer
56 views

$2 \ne 3$, but where's my error?

In $\mathbb{Z}_6$, $3^3 = 3^{-3}$ since $3^{-3} = 3^{6-3} = 3^3$. Thus $(3)^3 = (3^{-1})^3=2^3=2$. But also $3^3 = 3$ in $\mathbb{Z}_6$. Where's my error? Sorry for this question, but I think I got ...
1
vote
1answer
31 views

RSA Cryptography math problem

I have this math problem I'm kind of stuck on. You intercept the message 27284682555982882069237 which was encrypted using a public modulus of 124137798108168664109413 and an encryption ...
1
vote
1answer
41 views

Finding all integral solutions to a particular problem

Im working on some problems in Arthur Engel's problem solving strategies book and one of the problems is: On page 132: the question is: Now here is what the back of the book says: So I am ...
0
votes
0answers
8 views

Is not having a modular multiplicative inverse, the same thing as linear dependence in a vector of size 2x1?

It seems to me that for two numbers not having a modular multiplicative inverse and linear dependence in a 2x1 / 1x2 vector is related, is there a well known theorem / lemma on the relation between ...
0
votes
0answers
44 views

How to solve linear system of equation over a finite field

How can we solve linear system of equation over a finite field? I just found out about finite fields and i am having a hard time understanding solutions given on net. I know its equivalent to ...
0
votes
2answers
41 views

Why is it that $9w^2 ≡ 0 \pmod 4$ when $w>0$ is even?

Why is it that $9w^2 ≡ 0 \pmod 4$ when $w > 0$ is even? Say $w=2$; then you have $36 ≡ 0 \pmod 4$. The same thing if $w=6$; then you have $ 324 ≡ 0 \mod 4$. I dont see why, because $9 ≡ 1 \pmod ...
0
votes
1answer
6 views

How to return back element in Zp using pow?

For example I have value 2 2**17 % 31 = 4 4**23 % 31 = 2 And return value 2 What is the name of that equation, and how to find pairs like (17,23) over mod 31 ? ...
1
vote
0answers
41 views

Help with contradiction in proof of Euler's Theorem

The theorem states: if $n\in\mathbb{N}$ and $(a,n)=1$ then $$a^{\varphi (n)}\equiv 1\bmod n$$ Where $\varphi$ is the Euler-Phi function Take $a\in\mathbb{Z}$ such that $(a,n)=1$. Consider ...
2
votes
1answer
51 views

Number Theory: If $d\mid(4^n+1)$, show that $d$ is a sum of two squares

I have a proof for the following problem, but I'm not sure if it's correct: If $d\mid(4^n+1)$, show that $d$ is a sum of two squares. Proof $d\mid(4^n+1)\implies dm=4^n+1$, some $m\in\mathbb{Z}$. ...
0
votes
0answers
38 views

What are the solutions to $n^k \equiv k \mod m$?

Question: For a given modulus $m$ and base $n$, I am examining the set of solutions $\{k \in [0, m) \:\: | \:\: n^k \equiv k \mod m\}$. The case when $m$ is a power of 10 interests me the most. Why ...
1
vote
1answer
42 views

How do you solve a system of linear equations in modular arithmetic.

I'm finding a hard time trying to proceed with this cryptography problem: If i'm given such a system of linear equations: $3x+5y+7z\equiv3 (mod\ 16)$ $x+4y+13z\equiv5 (mod\ 16)$ $2x+7y+3z\equiv4 ...
3
votes
4answers
59 views

Number Theory: Find all incongruent solutions of $x^8\equiv3\pmod{13}$.

Find all incongruent solutions of $x^8\equiv3\pmod{13}$. I know that $2$ is a primitive root of $13$ and that $2^4\equiv3\pmod{13}$, so we want to solve $x^8\equiv2^4\pmod{13}$. Now, ...
0
votes
1answer
29 views

Congruence class solutions of linear equations

I'm not sure how to find the congruence class solutions of linear equations or systems of linear equations. For example, how would you solve $3x + 4y \equiv 4\pmod 6$?
1
vote
0answers
35 views

Number Theory: Find a primitive root of $13^{901}$ and find a complete set of primitive roots of $13$

I solved this problem: Find a complete set of mutually incongruent primitive roots of $13$. I know that there are $\phi(\phi(13))=4$ primitive roots of 13, which are $2,6,7,$ and $11$. However, I ...
3
votes
2answers
34 views

Number Theory: Show that $10^{3^n}\equiv 1\pmod{3^{n+2}}$ but $3^{n+3}\not\mid 10^{3^n}-1$

Show that for all $n\in\mathbb{N}$, $10^{3^n}\equiv 1\pmod{3^{n+2}}$ but $3^{n+3}\not\mid 10^{3^n}-1$. I think I've proved this problem, but I was unsure if my proof was correct: Proof Let $n=1$. ...
6
votes
2answers
29 views

Number Theory: Reordering $c_1,\dotsc,c_{10}$ so that $(2k-1)\mid(a_k-b_k)$

I have this homework problem that I'm confused on how to do: Given any distinct $z_1,\dotsc,z_{10}\in\mathbb{Z}$, show that one can reorder these as $s_5,s_4,\dots,s_1,t_5,\dotsc,t_1$ so that ...
4
votes
3answers
50 views

Number Theory: Find $m\equiv 1\pmod4$ so that $x^2\equiv -1\pmod{m}$ has no solution.

I have this problem that I'm a bit stuck on: Find $m\equiv 1\pmod4$ so that $x^2\equiv -1\pmod{m}$ has no solution in $\mathbb{Z}$. So far, I know that $m$ can't be prime because $(\frac{-1}{p})=1$, ...
6
votes
2answers
93 views

What is the remainder of $\frac{2^{2015}}{36}$?

I am unfamiliar with modular arithmetic. I am attempting to solve this problem as practice for mathleague competitions. In an attempt to solve this problem, I first attempted to define what the ...