1
vote
1answer
22 views

Question on Cardinality ..Help

a) Let $n$ be a positive integer. Define a relation on $\mathbb{Z} $, which yields a partition of $\mathbb{Z}$ with $n$ elements; and give the partition. b) Deduce that $n\omega = \omega$ where ...
1
vote
0answers
45 views

Is this theorem provable using relatively elementary number theory and abstract algebra?

$\textbf{Theorem}$: Let $p$ be a prime. Let $q$ be a prime that doesn't divide $p - 1$, so that $\mathbb{F}_p$ does have an element of order $q$. Let $\zeta$ be an imaginary number whose order is $q$. ...
3
votes
1answer
36 views

$4|(p-1) \implies$ there is an element $x$ of order $ 4$ modulo $p$.?

"$p \equiv 1 \mod 4 \implies 4 \mid (p-1) \implies$ there is an element $x$ of order $4$ modulo $p$." I am having a difficult time understanding why this implies there is an element $x$ of order $4$. ...
3
votes
2answers
77 views

My professor says that this equation in a finite field has a solution but I don't think it does.

More than likely it is I who is mistaken, but is there a chance that my professor made a mistake in the following problem? We are tasked with: Let $p = 3$. We do not have an element of order $5$ in ...
2
votes
0answers
29 views

How do i prove that $\gcd(a_1,\ldots,a_n)\operatorname{lcm}(a_1,\ldots,a_n)=a_1\cdots a_n$?

Let $a_1,\ldots,a_n$ be nonzero integers. Define $$G=\{A\in\mathbb{Z}:A \text{ is a linear combination of } a_1,\ldots a_n\}$$ My definition for $\gcd(a_1,\ldots,a_n)$ is the principal ideal of $G$. ...
1
vote
1answer
28 views

Is there a generalization of the twin prime conjecture to rings or certain rings?

The question's in the title. For instance, if $R$ contains $2$ then there are an infinite number of pairs of prime principal ideals $(p),(q)$ such that $p = q + 2$. I just made that up and it's ...
0
votes
5answers
107 views

Is this a true theorem? [closed]

I'm trying to prove the existence of the following theorem: If $n,p \in \mathbb{N}$, then $(p+1)^n = 1 \mod p$ Is this theorem true? I think it is, but I don't know how to prove it! Thanks!
1
vote
2answers
39 views

Given a finite abelian group $G$ with $g \in G$, then for any divisor $d$ of $|g|$ there is an element of $G$ with order $d$.

From an homework question that comes as an introduction to abelian groups. Regarding my efforts to solve the question, I have been trying to utilize the fundamental theorem of finite abelian groups, ...
1
vote
2answers
80 views

Number Theory and Cryptography

I am a math tutor at a community college, and I stopped in to ask one of the professors a question about crypto and he lent me a graduate level book on for a full year course in the title of this ...
0
votes
1answer
39 views

Proving a set of coordinates is a group.

Here is a homework problem I have from my Abstract Algebra - Number Theory class. I've reprinted it verbatim. I'm a little uncertain how to approach this problem given that the elements of the set $G$ ...
1
vote
0answers
60 views

Proposition 17, p. 68 of Lang's Algebraic Number Theory

I'm stuck on a detail of the following propositon: Let $K, E$ be linearly disjoint number fields with degrees $n$ and $m$ over $\mathbb{Q}$ whose discriminants (over $\mathbb{Q}$) are relatively ...
0
votes
1answer
42 views

Can one freely take the discrete logarithm of an element in a subset of a finite field?

Consider $\mathbb{F}_p^\times$ and $S = \{a \in \mathbb{F}_p^\times : a^n \equiv 1 \mod p\}$ for any $n$. Suppose I have $a \in S$. If I also have that $a^j \equiv a^k \mod p$, can I just take the ...
2
votes
1answer
49 views

Sum of Three squares

Considering $z=a+bi+cj$ ($a,b,c\in\mathbb{Z}$) and $w=d+ei+fj$ ($d,e,f\in\mathbb{Z}$) and the property of complex numbers that $|zw|=|z||w|$. If the rule of multiplication $zw$ is defined such that ...
1
vote
2answers
24 views

Regarding unique factorization in a polynomial ring and irreducibles

I believe I'm not correctly understanding the concept of unique factorization and irreducibles. Consider $R = \mathbb{F}_7$ and $h \in R[x]$ where $h = x^4 + 4x^3 + 3x^2 + 5x + 6$. Now $h$ has the ...
1
vote
0answers
40 views

A simple equivalence relation problem

For the set of all subsets of R, let $A \sim B$ mean that $A \subseteq B$ ($A$ is a subset of $B$). Question: Is this an equivalence relation? If not explain why. Attempt at solution: Reflexive- If ...
0
votes
1answer
19 views

Proving that $mx \equiv 0 \pmod n$ has $\gcd(m, n)$ solutions in the interval $[0, n-1]$

I wish to prove, using my own intuition, that there are $\gcd(m, n)$ group homomorphisms from $\mathbb{Z}_m$ to $\mathbb{Z}_n$. I have reduced(?!) the problem to proving that there are $\gcd(m, n)$ ...
1
vote
2answers
37 views

Reciprocity problem in I&R “A Classical Introduction in Modern Number Theory”

Let $\pi = a+bi \in \mathbb{Z}[i]$ and $q \equiv 3 \pmod{4}$ a rational prime. Show that $\pi^q \equiv \bar{\pi} \pmod{q}.$ It's a problem from chapter 9 "cubic and biquadratic reciprocity" of ...
0
votes
0answers
50 views

Show that the number of elements in the equivalence class is n?

Question is : Let $G$ be a finiote group of order n = $p^{\alpha}$m, where $p$ is a prime number and if $p^r$ | m but $p^{r+1} \nmid$ m Let $\mathcal M$ be the set of all subset of $G$ which have ...
0
votes
1answer
51 views

Proving Legendre's Formula

Where $v_p(n)$ is called the $p$-adic valuation of $n$. prove $v_p(n!)=\sum_{t=1}^\infty \left\lfloor \frac{n}{p^t} \right\rfloor$ so far i have that $v_p(n!) = v_p(n) + v_p(n-1) + \cdots + v_p(2) + ...
2
votes
2answers
39 views

Prove that if $(u,v)$ is chosen randomly from $S$, there is at least a $50\%$ chance that $u\ne\pm v \bmod N$

I need serious help with this problem. Suppose $N$ is an odd composite number and $S=\{(x,y) \in \mathbb Z^2 : x^2 \equiv y^2 \mod N\}$ Prove that if $(u,v)$ is chosen randomly from $S$, there is ...
2
votes
5answers
91 views

How do you Compute $7^{1000} \mod 24$?

I'm being asked to compute $7^{1000} \mod 24$. I have Fermat's Little Theorem and Euler's Theorem. How do I use these to compute $7^{1000} \mod 24$? I'm stuck because $24$ is not prime. In this case, ...
1
vote
2answers
30 views

Abstract Algebra/Elementary Number Theory Computation

Compute $2^{2^{17}}+1$ mod $19$. (hint: compute first $2^{17}$ mod $18$) Using the fact that there are $6$ numbers coprime to $18$, I got that $$2^{17}\; \mathrm{mod}\;\; 18 = 2^6 \cdot 2^6 ...
0
votes
1answer
37 views

Divisors of $2^n-1$ and primitivity in $F_{2^n}$

Is there a classical (and efficient) algorithm to find all divisors of $2^n-1$ ? This question comes to me when I tried to easily determine if some element $e$ of the finite field $F_2[X]/P(X)\equiv ...
2
votes
2answers
66 views

Prove that $r_1 = r_2$ iff $n | (b - a)$

I need to know if I'm clear in my proof since I will have to present the answer to my class. Here's the full question: Let $n$ be a fixed positive integer. Then for any integers $a$ and $b$, let ...
1
vote
3answers
52 views

zeroes to polynomials in residue rings of Z

I'm supposed to find zeroes of $x^{12} -16$ in $\mathbb Z_{17}$, seems simple enough but I just can't seem to make any progress. I realize of course that we have $X^{12} = -1$ in $\mathbb Z_{17}$, ...
10
votes
4answers
240 views

Prove: If $\gcd(a,b,c)=1$ then there exists $z$ such that $\gcd(az+b,c) = 1$

I can't crack this one. Prove: If $\gcd(a,b,c)=1$ then there exists $z$ such that $\gcd(az+b,c) = 1$ (the only constraint is that $a,b,c,z \in \mathbb{Z}$).
0
votes
2answers
82 views

Prove $\forall a,b \in \mathbb R, \ b \neq 0 \ \exists c \in \mathbb R : a / b = c$

Prove $$\forall a,b \in \mathbb R, \ b \neq 0 \ \exists c \in \mathbb R : a / b = c$$ I've been thinking how to prove the above statement that most people assume to be true. Should one prove there ...
2
votes
2answers
64 views

Fast way of calculating the order of an element in $\mathbb{Z}_n$?

Is there a fast way of calculating the order of an element in $\mathbb{Z}_n$? If i'm asked to calculate the order of $12 \in \mathbb{Z}_{22}$ I just sit there adding $12$ to itself and seeing if the ...
3
votes
2answers
49 views

Let $F$ be a field with $4$ elements. Show $1+\alpha+\alpha^2 = 0$ for $\alpha \in F$ and $X^2 + \alpha$ is reducible in $F[X]$

Let $F$ be a field with $4$ elements and let $\alpha \in F$ be an element $\neq 0, 1$. a) Show that $F = \{0,1,\alpha, \alpha^2\}$ and $1 + \alpha + \alpha^2 = 0$: I know that $F^* = F - \{0\}$ is a ...
1
vote
1answer
59 views

Quadratic residues and kernel of a homomorphism

Show that if $p\equiv 3 \pmod 4$ is a prime, exactly one between $2$ and $-2$ is a quadratic residue modulo $p$. The "most obvious" solution is the following: since $\displaystyle \left(\frac{-1}{p} ...
6
votes
3answers
67 views

Let $R = \mathbb Z[i]$. Show $I \cap \mathbb Z$ is an ideal in $\mathbb Z$, for all $a \in I \cap \mathbb Z$, $10 \mid a^2 = N(a)$.

Let $R = \mathbb Z[i]$, $z = 3+i$ and $I = \langle z \rangle$. I need to show $I \cap \mathbb Z$ is an ideal in $\mathbb Z$, for all $a \in I \cap \mathbb Z$, $10 \mid a^2 = N(a)$ and $10 \mid a$, ...
0
votes
2answers
68 views

Let $\phi: G \rightarrow G$ be given by $\phi(g)=g^2, g\in G$. Show that if $|G|$ is odd, then $\phi$ is an automorphism

Let $G$ be an abelian group of order $|G| < \infty$. Let $\phi: G \rightarrow G$ be given by $\phi(g)=g^2, g\in G$. Show that if $|G|$ is odd, then $\phi$ is an automorphism: I consider $a ...
1
vote
1answer
60 views

Let $\tau_1, \tau_2 \in A_6$ be permutations with cycle-type $(2, 4)$. Show there exists $\tau \in A_6: \tau \tau_1 \tau^{-1} = \tau_2.$

Let $\tau_1, \tau_2 \in A_6$ be permutations with cycle-type $(2, 4)$. Show there exists $$\tau \in A_6\mid \tau \tau_1 \tau^{-1} = \tau_2$$ I know $\tau_1 = (a b c d)(e f)$ and $\tau_2 = ...
3
votes
1answer
23 views

Finding an $i \in \mathbb{N}$ s.t. $im + k = p$

Let $m,k \in \mathbb{N}$ s.t. $\gcd(m,k) = 1$. Let $\pi$ be a prime positive integer. Question: Does there always exist an $i \in \mathbb{N}$ s.t. $im + k = p$ s.t. $p$ is a prime positive integer ...
2
votes
2answers
77 views

Let $R = \mathbb F_3[X]/\langle X^3 + X^2 + 1\rangle$ and $\alpha = [X] \in R$. Show $R^*$ is not cyclic.

Let $R = \mathbb F_3[X]/\langle X^3 + X^2 + 1\rangle$ and $\alpha = [X] \in R$. Show $R^*$ is not cyclic. I've proven: $X^3+ X^2 + a \in \mathbb F_3[X]$ is irreducible $\iff$ $a=2$. $\alpha \in ...
0
votes
1answer
43 views

Show $x^2 \equiv 94 \pmod{195}$ if and only if $x^2 \equiv 1 \pmod 3$, $x^2 \equiv 4 \pmod 5$ , $x^2 \equiv 3 \pmod{13}$

Show $x^2 \equiv 94\pmod {195}$ if and only if $x^2 \equiv 1 \pmod 3$, $x^2 \equiv 4 \pmod 5$ , $x^2 \equiv 3 \pmod {13}$ I've already proved $x^2 \equiv 94 \pmod {195}$ implies $x^2 \equiv 1 ...
0
votes
0answers
48 views

Showing a Prime Integer Divides the Content of an Integer Polynomial

Setting: $f = a_0 + a_1 x + \ldots + a_n x^n \in \mathbb{Z}[x]$ $g = x^m - 1 \in \mathbb{Z}[x]$ $f \mid g$ $f^{(i)} = f(x^i) = a_0 + a_1 x^i + \ldots + a_n (x^i)^n \in \mathbb{Z}[x]$ for all $i \in ...
0
votes
1answer
45 views

Prove: the canonical ringhomomorphism $f: \mathbb Z \rightarrow R/I = \mathbb Z[i]/ \langle5+3i \rangle$ is surjective.

Let $R = \mathbb Z[i]$, $z=5+3i$ and $I=\langle z\rangle$. I've shown: $z$ is not a prime element in $R$ $R/I$ is not a field $1+i\notin R^*$ $(5+3i)/(1+i) \in R$ $-21+i \in I$ To prove: The ...
1
vote
1answer
54 views

existence of element of multiplicative order $4$ in $\mathbb{Z_p}$, if $p \equiv 1 \pmod4$, where $p$ is prime.

Assume that $p \equiv 1 \pmod4$, where $p$ is prime. The multiplicative group of the finite field $\mathbb{Z_p}$ is cyclic and is of order $p-1$. We know that $4$ is a divisor of $p-1$. Now my text ...
0
votes
2answers
52 views

Show $\phi: \mathbb F_3 \times \mathbb F_3 \rightarrow R$ given by $\phi(a,b) = a\epsilon_1 +b\epsilon_2$ is bijective, $a,b \in \mathbb F_3$

Show $\phi: \mathbb F_3 \times\mathbb F_3 \rightarrow R$ given by $\phi(a,b) = a\epsilon_1 +b\epsilon_2$ is bijective, $a,b \in \mathbb F_3$. $R = \mathbb F_3[X]/\langle X^2 -1\rangle$ and ...
1
vote
1answer
37 views

Prove that $\left(\frac2p\right) = 1$ if $p \equiv 1,7 \pmod 8$ and $\left(\frac2p\right) = -1$ if $p \equiv 3,5 \pmod 8$ using ring theory

Let $p$ be an odd prime number and let $\alpha = [X] \in R=\mathbb F_p[X]/\langle X^4+1\rangle$, and $y = \alpha + \alpha^{-1}$ I've proven: 1) $\alpha$ is a primitive eight root of unity in $R$. ...
1
vote
2answers
58 views

$x^2=37\pmod {77}$ is there solution for $x$?

Is there solution for $x$? $$x^2=37\pmod {77}$$ Which method should we use, Diophant equations or? I found nothing by using induction. thanks
1
vote
2answers
43 views

Chinese Remainder Theorem with coprime congruences

Suppose that $(a,m)=1$ and $(b,n)=1$, where $(x,y)$ denotes the greatest common divisor of $x$ and $y$. Show that if $$ c \equiv a \pmod{m} \\ c \equiv b \pmod{n} \\ $$ then $(c,mn)=1$. I've tried to ...
4
votes
2answers
65 views

How to prove that $a^{2^{n-2}} \equiv 1 \pmod{2^n}$?

Let $a$ be an odd integer and $n$ an integer such that $n\ge 3$. 1) I want to show that $a^{2^{n-2}} \equiv 1 \pmod{2^n}$ 2) Then I want to show that $(\mathbb Z/{2^n\mathbb Z})^*$, the ...
0
votes
0answers
37 views

Polynomial Division in $R[X]$ - Why does one assume the leading coefficient $a_n$ of $d$ is not zero divisor?

Polynomial Division in $R[X]$ - Why does one assume the leading coefficient $a_n$ of $d$ is not zero divisor ? The algorithm (theorem) states that for $f, d \in R[X]$, leading coefficient $a_n$ of ...
2
votes
3answers
57 views

Let $L = \mathbb F_2[X]/\langle X^4 + X + 1 \rangle$ is a field. Show $L^* = L / \{0\} = \langle X \rangle$ is cyclic.

Let $L = \mathbb F_2[X]/\langle X^4 + X + 1 \rangle$ is a field. Show $L^* = L / \{0\} = \langle X \rangle$ is cyclic. I've proven that $X^4 + X + 1$ is irreducible, so $L$ is a field. I also know ...
1
vote
0answers
41 views

Show that the field $L = \mathbb F_3[X]/\langle X^5 - X + 1\rangle$ consists of $243$ elements and that $[X][f] = [1]$ for some $[f] \in L$.

Show that the field $L = \mathbb F_3[X]/\langle X^5 - X + 1\rangle$ consists of $243$ elements and that $[X][f] = [1]$ for some $[f] \in L$. I know that $L$ is a ring, so it is also a group with ...
1
vote
0answers
57 views

Let $f \in \mathbb F_3[X]$ be reducible, degree 4 or 5 and no roots, then a monic irreducible polynomial exists of degree 2 dividing $f$

Let $f \in \mathbb F_3[X]$ be reducible, degree 4 or 5 and no roots, then a monic irreducible polynomial exists of degree 2 dividing $f$. I've proved that $X^2 + 1, X^2 + X + 2, X^2 + 2X + 2$ are ...
1
vote
1answer
99 views

ABC Conjecture: Simple example showing $\epsilon$ is necessary

I was looking over Lang's discussion of the abc conjecture in his famous Algebra tome. He says We have to give examples such that for all $C>0$ there exist natural numbers $a$,$b$, $c$ ...
0
votes
1answer
171 views

Do I have this right? Are these conclusions valid in this isomorphic view of $\Bbb{R}$?

Let $F = (\Bbb{R}, \oplus_d, \cdot)$ be the field with usual $\cdot$, and $\oplus_d$ is defined as $a \oplus b = (\sqrt[d]{a} + \sqrt[d]{b})^d$. This field is isomorphic to usual $\Bbb{R}$ structure ...