Happy Thanksgiving! Please note that there are no classes November 25th-December 1st.

MIT PRIMES/Art of Problem Solving

CROWDMATH 2024: Generalizations of the Notion of Primes

a
p
Generalizations of the Notion of Primes J
Exercise 0.4
j B k k N
The post below has been deleted. Click to close.
This post has been deleted. Click here to see post.
Thayaden
1135 posts
#1
This topic is linked to null - null.
Y by
In general, $\mathbb{Z}_n$ is a ring. A ring is and integral domain iff $0$ is the only zero-divisor. Another way of putting this is for some prime number $p$ show that,
$$ ab \not \equiv 0\pmod{p}$$where $a,b\in \mathbb{Z}_n$ where $a,b\not\equiv 0$. Consider $ab\equiv 0\pmod{p}$ for some $a,b\in\mathbb{Z}_n$ where $p$ is still some prime number. This implies $p|ab$ although by definition $p|pk$ ONLY for some $k\in \mathbb{Z}$ this implies that either $a=p$ or $b\equiv p$ although in modulus $p$ we have $p\equiv 0$ thus $a$ or $b$ must be a zero-divisor thus we can conclude that for any given prime $n$ $\mathbb{Z}_n$ is an integral domain. Consider $n=xy$ if we have $ab\equiv 0\pmod{n}$ that implies that $ab|xy$, in this case, $a=x$ or $a=y$ where $b$ is equal to the other that implies that $x$ is a zero divisor and if $n$ is non-prime that implies that for some non-$0$ divisor, $x$ is a zero divisor.
This post has been edited 3 times. Last edited by Thayaden, Nov 7, 2024, 6:51 PM
Z K Y
The post below has been deleted. Click to close.
This post has been deleted. Click here to see post.
felixgotti
182 posts
#2
Y by
Hi Thayaden,

Your notation is a bit confusing. Does $ab \mid p$ mean "$p$ divides $ab$"?
This post has been edited 1 time. Last edited by felixgotti, Oct 31, 2024, 11:36 PM
Z K Y
The post below has been deleted. Click to close.
This post has been deleted. Click here to see post.
Thayaden
1135 posts
#4 • 1 Y
Y by felixgotti
felixgotti wrote:
Hi Thayaden,

Your notation is a bit confusing. Does $ab \mid p$ mean "$p$ divides $ab$"?

the above proof is wrong I made some assumptions thank you for pointing that out. A simpler proof might go as follows:

Suppose $\mathbb{Z}_n$ is not an integral domain thus we might say that $ab\equiv 0\pmod{n}$ where $a\neq 0$ and $b\neq 0$ such that $a,b\in\mathbb{Z}_n$

If n is prime:
Recall that for any residue $k$ in a mod $m$ system then $k^{-1}$ exists such that $k$ and $m$ are relatively prime. Recall since $a\neq 0$ then $a$ does have an inverse and we can multiply $a^{-1}$ in,
$$ab\equiv 0\pmod{n},$$Since we are assuming $\mathbb{Z}_n$ is indeed not an integral domain. We have,
$$b\equiv 0\pmod{n},$$but recall we had $b\neq 0$ where $b\in\mathbb{Z}_n$ so a contradiction arises to the assumption that $\mathbb{Z}_n$ is not an integral domain when $n$ is prime. Therefore when $n$ is prime $\mathbb{Z}_n$ is an integral domain.
n is composite:
Let $n=xy$ such that $x,y\neq0$ and $x,y\in \mathbb{Z}_n$. Recall that,
$$n\equiv 0\pmod{n}$$thus,
$$xy\equiv 0\pmod{n}$$As $x$ and $y$ are non-zero yet the product forms zero then $\mathbb{Z}_n$ is an integral domain iff $n$ is prime.
Z K Y
The post below has been deleted. Click to close.
This post has been deleted. Click here to see post.
felixgotti
182 posts
#5
Y by
Your argument appears correct. To enhance clarity, consider discussing each implication separately.
Z K Y
N Quick Reply
G
H
=
Page Feed | J
Linked Item Topics
G
Topic
First Poster
Last Poster
H
Exercise 0.4
Thayaden   3
N Nov 9, 2024 by felixgotti
In general, $\mathbb{Z}_n$ is a ring. A ring is and integral domain iff $0$ is the only zero-divisor. Another way of putting this is for some prime number $p$ show that,
$$ ab \not \equiv 0\pmod{p}$$where $a,b\in \mathbb{Z}_n$ where $a,b\not\equiv 0$. Consider $ab\equiv 0\pmod{p}$ for some $a,b\in\mathbb{Z}_n$ where $p$ is still some prime number. This implies $p|ab$ although by definition $p|pk$ ONLY for some $k\in \mathbb{Z}$ this implies that either $a=p$ or $b\equiv p$ although in modulus $p$ we have $p\equiv 0$ thus $a$ or $b$ must be a zero-divisor thus we can conclude that for any given prime $n$ $\mathbb{Z}_n$ is an integral domain. Consider $n=xy$ if we have $ab\equiv 0\pmod{n}$ that implies that $ab|xy$, in this case, $a=x$ or $a=y$ where $b$ is equal to the other that implies that $x$ is a zero divisor and if $n$ is non-prime that implies that for some non-$0$ divisor, $x$ is a zero divisor.
3 replies
Thayaden
Sep 18, 2024
felixgotti
Nov 9, 2024
J
H
Exercise 0.4
elee310   0
Jul 29, 2024
What I've tried so far:

$\text{The ring } \mathbb{Z}/n\mathbb{Z} \text{ s.t. } n \not \in \mathbb{P} \text{ is the set } \{ 0, 1, 2, \cdots, n-2, n-1 \}$
$\text{Since n is not prime, it can be prime factorized into the form } n=\prod_{i=1}^{k} p_{i}^{e_{i}}$
$\text{This implies that there will be } a,b \leq n \text{ s.t. } a*b=b*a=n \rightarrow a*b \equiv 0 \text{ (mod n)}$
$\therefore \forall n \notin \mathbb{P} \text{ a,b s.t. } a*b=n \text{ are zero divisors of } \mathbb{Z}/n\mathbb{Z}$
$\forall p \in \mathbb{P}, n=1 \lor n=p \mid p \rightarrow \forall a,b \in \mathbb{Z}/p\mathbb{Z} \text{ s.t. } gcd(a,p) =1 \land gcd(b,p) =1 \text{ } p \nmid a*b \rightarrow a*b \not \equiv 0 \text{ (mod p)}$
$\therefore \forall n_{1},n_{2} \in \mathbb{Z}/p\mathbb{Z} n_{1}*n_{2}=0  \leftrightarrow n_{1} \equiv 0 \lor n_{2} \equiv 0, \text{meaning 0 is the only zero divisor.}$
Where I'm stuck:
0 replies
elee310
Jul 29, 2024
0 replies
J
No more topics!
H
J
H
Exercise 0.4
Thayaden   3
N Nov 9, 2024 by felixgotti
In general, $\mathbb{Z}_n$ is a ring. A ring is and integral domain iff $0$ is the only zero-divisor. Another way of putting this is for some prime number $p$ show that,
$$ ab \not \equiv 0\pmod{p}$$where $a,b\in \mathbb{Z}_n$ where $a,b\not\equiv 0$. Consider $ab\equiv 0\pmod{p}$ for some $a,b\in\mathbb{Z}_n$ where $p$ is still some prime number. This implies $p|ab$ although by definition $p|pk$ ONLY for some $k\in \mathbb{Z}$ this implies that either $a=p$ or $b\equiv p$ although in modulus $p$ we have $p\equiv 0$ thus $a$ or $b$ must be a zero-divisor thus we can conclude that for any given prime $n$ $\mathbb{Z}_n$ is an integral domain. Consider $n=xy$ if we have $ab\equiv 0\pmod{n}$ that implies that $ab|xy$, in this case, $a=x$ or $a=y$ where $b$ is equal to the other that implies that $x$ is a zero divisor and if $n$ is non-prime that implies that for some non-$0$ divisor, $x$ is a zero divisor.
3 replies
Thayaden
Sep 18, 2024
felixgotti
Nov 9, 2024
J