The time is now - Spring classes are filling up!

MIT PRIMES/Art of Problem Solving

CROWDMATH 2024: Generalizations of the Notion of Primes

G
Topic
First Poster
Last Poster
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
Exercise 0.3
Thayaden   2
N Nov 7, 2024 by Thayaden
Crazy Idea but $(M,\gcd )$ I think the condtions work

$$\gcd(3,7)=\gcd(7,3)$$and
$$\gcd(3,7)=\gcd(3,101)$$yet
$$7\neq101$$
2 replies
Thayaden
Sep 16, 2024
Thayaden
Nov 7, 2024
Exercise 0.8
Thayaden   1
N Oct 31, 2024 by felixgotti
Consider $f(x)\in R[x]$ and such that $f^{-1}(x)\in R[x]$ we clearly see that,
$$f(x)\cdot f^{-1}(x)=1$$Recall $\text{deg}(1)=0$ thus $\text{deg}(f(x)\cdot f^{-1}(x))=1$ we can clearly see that as they are each other inverse that $\deg(f)=\deg(f^{-1})=1$ thus let,
\begin{align*}
f(x)&= a,\\
f^{-1}&=b.
\end{align*}Thus we see,
$$a\cdot b=1$$In other words $a$ and $b$ are elements in the group of units of $R[x]$ although since $f(x),f^{-1}(x)\in R$ it is also the group of units of $R$ therefor $R[x]^{\times}=R^{\times}$
1 reply
Thayaden
Oct 17, 2024
felixgotti
Oct 31, 2024
units...
Thayaden   1
N Oct 31, 2024 by felixgotti
Part 1:
Notice $\mathbb{Z}^{\times}=\{\pm1 \}$ thus for $\mathbb{Z}[i]$ we might enharite this too. This might be easily proven by letting the coefficient of the unreal part be $0$. Thus we might know that at least $\pm1$ is a unit. Taking that idea once again letting the real part be $0$ we have,
$$i\cdot-i=-(i^2)=1$$Thus as we are communitive $\pm i$ is in the set this makes sense from an algebraic perspective on the complex plane when multiplying a unit we have a change of direction likewise this is also true for real numbers thus $\mathbb{Z}[i]^{\times}=\{\pm1,\pm i \}$
1 reply
Thayaden
Sep 25, 2024
felixgotti
Oct 31, 2024
Exercise 0.5 crazy
Thayaden   1
N Oct 31, 2024 by felixgotti
Let $S$ be a finite integral domain that is not a field. For some $t\in S \not\ \{ 0\}$ there is no $t^{-1}\in S$ for some many $t$ as $R$ is not a field. Consider the powers of $t$,
$$t,t^2,t^3,t^4, ...$$let,
$$\underbrace{t,t^2,t^3,...,t^{|S|}}_{|S|},t^{|S|+1}$$Consider the first $|S|$ powers as unique, implying that $t^{|S|+1}$ is not unique or consider the first $|S|$ as not unique. In any given case for some $m>n$,
$$t^m=t^n$$$$t^m-t^n=0$$$$t^n \cdot (t^{m-n}-1)=0$$If $t^n=0$ that implies that $t=0$ (this can be shown inductively) and we know that $t \neq 0$ so that implies that,
$$t^{m-n}-1=0$$$$t^{m-n}=1$$$$t^{m-n-1}\cdot t=1$$Although that implies that $t$ has an inverse, that begins $t^{m-n-1}$ the only numbers that could not have an inverse indeed do have an inverse thus all numbers in $S$ have an inverse thus $S$ is a field!
1 reply
Thayaden
Sep 24, 2024
felixgotti
Oct 31, 2024
Exercise 0.7
Thayaden   0
Oct 2, 2024
If $R$ is an intergral domain then $R[x]$ is too,
Let $f(x),g(x)\in R[x]$ such that they are non zero, denote
$$f(x)=\sum_{i=0}^{n}{a_{i}x^{i}}$$$$g(x)=\sum_{j=0}^{m}{b_{j}x^{j}}$$Taking $f(x)g(x)$ let $c_{m+n}=a_{n}b_{m}$ be the leading coefficient of $f(x)g(x)$. Notice that $a_n,b_m\neq 0$ thus $c_{m+n}\neq0$ so in short for $p(x)\in R[x]$ the leading coefficient of $p(x)$ cannot be $0$ thus $R[x]$ must be an integral domain.
Going the other way say $R[x]$ is an integral domain,
For the sake of contradiction let $ab=0$ such that $a,b\in R$ and $a,b\neq0$, let $f(x)=a, g(x)=b\in R[x]$ taking there product,
$$f(x)g(x)=ab=0$$This contradicts our previous statement thus $R$ is an integral domain!
Finally iff $R$ is an integral domain then $R[x]$ must also be an integral domain $\blacksquare$
0 replies
Thayaden
Oct 2, 2024
0 replies
Exercise 0.2
Thayaden   0
Sep 16, 2024
Let $\{S_a \}_{a\in n}$ be a submonoid of $M$, where $a$ runs over $n$ is the index set. Let $S$ be the intersection of all possible submonoids of $M$. Notice now we just need to prove $S\subseteq M$. Let $e$ be the identity of $M$ notice that $e \in S_a$ and in turn $e\in S$ therfor $S$ has the identity of $M$ the first characteristic of a submonoid. Now we just need to prove that it is a monoid with respect to the operation of $M$. Let $p,q \in S$ by intersection rules $p\in S_a$ and $q \in S_a$ and notice $S_a$ is a submonoid in itself and thus the operation $p*q\in S_a$ for every $a$ thus $p*q\in S$ by intersection rules again. Thus $S$ is a submonoid in itself!

Let $\{S_a \}_{a\in n}$ be a subgroup of $M$, where $a$ runs over $n$ is the index set. Let $S$ be the intersection of all possible subgroups of $M$. Notice now we just need to prove $S\subseteq M$. Let $e$ be the identity of $M$ notice that $e \in S_a$ and in turn $e\in S$ therfor $S$ has the identity of $M$ the first characteristic of a subgroup. Now we need to prove that it is a subgroup with respect to the operation of $M$. Let $p,q \in S$ by intersection rules $p\in S_a$ and $q \in S_a$ and notice $S_a$ is a subgroup in itself and thus the operation $p*q\in S_a$ for every $a$ thus $p*q\in S$ by intersection rules again. Finally, we need to show that every element has an inverse. Let $x\in S$ and let $x^{-1}$ represent the inverse of $x$. Notice if $x\in S$ then it follows that $x\in S_a$ although notice that all $S_a$ are subgroups of $M$ and thus $x^{-1}\in S_a$ and since $x^{-1}\in S_a$ for any $a\in n$ then by intersection $x^{-1}\in S$ thus $S$ is a subgroup of $M$
0 replies
Thayaden
Sep 16, 2024
0 replies
Exercise 0.1(part 1)
Thayaden   1
N Sep 11, 2024 by Thayaden
let $b\in M$ by definition,
$$(1):~~e*b=b*e=b,$$$$(2):~~e'*b=b*e'=b$$this is true for all $b$ thus let $b=e'$ this might lead us to (from $(1)$),
$$e*e'=e'*e=e'$$$$e*e'=e'$$Now let $b=e$ (using $(2)$),
$$e'*e=e*e'=e$$$$e*e'=e$$By the transitive property,
$$\boxed{e'=e}$$as the first condition is true, $e,e'\in M$ we might then say that given all identity elements of $M$ denoted as $e_i$ we might have,
$$e_1=e_2$$and inductively,
$$e_k=e_{k+1}$$thus,
$$e_1=e_2=e_3=e_4=\cdots$$. Or in plain text, we might say that as one identity is equal to another then if we have some identity it is the same as the identity we already have.
1 reply
Thayaden
Sep 11, 2024
Thayaden
Sep 11, 2024
Exercise 3.4
FoxProdigy   1
N Aug 19, 2024 by felixgotti
Problem Statement: Prove that a monoid is a GL-monoid if and only if it is prime-like.

Proof:

Prime-like$\implies$ GL:
Let $M$ be a prime-like monoid. Suppose $a, b, c \in M$ such that $\text{gcd}(a, b) = \text{gcd}(a, c) = 1$. Suppose further towards a contradiction that $\text{gcd}(a, bc) \neq 1$; that is, that there exists some divisor $d \mid a$ with $d \mid bc$. Then because $M$ is prime-like, $d$ has some divisor $e$ with either $e \mid b$ or $e \mid c$. Either way, we also must have $e \mid a$, which means that either $\text{gcd}(a, b) \neq 1$ or $\text{gcd}(a, c) \neq 1$. This is a contradiction. Thus, $\text{gcd}(a, bc) = 1$, which means $M$ is GL.

GL$\implies$ prime-like:
Let $M$ be a GL monoid, and suppose $a, b, c \in M$ with $a \mid bc$. Assume towards a contradiction that for all $d \mid a$, $d \nmid b$ and $d \nmid c$ (in other words, $a$ shares no divisors with $b$ or $c$). This implies that $\text{gcd}(a, b) = \text{gcd}(a, c) = 1$. Since $M$ is GL, this means that $\text{gcd}(a, bc) = 1$. This contradicts the assumption that $a \mid bc$. Thus, there must exist some $d \mid a$ with $d \mid b$ or $d \mid c$, which means $M$ is prime-like.
1 reply
FoxProdigy
Aug 3, 2024
felixgotti
Aug 19, 2024
Exercise 0.1
palindrome868   0
Aug 5, 2024
What I've tried so far:

(1) If $e, e' \in M$ are two distinct identity elements of $M$, then $e * e' = e = e'$, a contradiction.

(2) Let $e$ be the identity element of $M$. If $v, v' \in M$ are two distinct inverses of $u$, then
\begin{align*}
v * u = e &\implies (v * u) * v' = (e) * v' \\
&\implies v * (u * v') = v' \\
&\implies v = v'
\end{align*}a contradiction.

(3) Claim 1: Associativity holds in $\mathcal{U}{(M)}$

$b, c, d \in \mathcal{U}{(M)} \implies b, c, d \in M \implies (b * c) * d = b * (c * d)$.

Claim 2: Identity holds in $\mathcal{U}{(M)}$

The identity element of $M$ is the inverse of itself, so it is also in $\mathcal{U}{(M)}$. Since the operations in $M$ and $\mathcal{U}{(M)}$ are the same, it is the identity of $\mathcal{U}{(M)}$ as well.

Claim 3: Closure holds in $\mathcal{U}{(M)}$

Let the identity element be $e$.
$a, b \in \mathcal{U}{(M)} \implies a, b \in M \implies a*b \in M$.
$(a*b)*(b^{-1} * a^{-1}) = a * a^{-1} = e$, so $a*b$ is invertible (namely, its inverse is $b^{-1} * a^{-1}$), which implies $a*b \in \mathcal{U}{(M)}$.

Claim 4: Every element in $\mathcal{U}{(M)}$ has an inverse

This is true by the definition of $\mathcal{U}{(M)}$.

By definition, these four claims are sufficient to determine $\mathcal{U}{(M)}$ is a group.

Where I'm stuck:

Please check :)
0 replies
palindrome868
Aug 5, 2024
0 replies
Exercise 0.3
j G H J
G H BBookmark kLocked kLocked NReply
The post below has been deleted. Click to close.
This post has been deleted. Click here to see post.
Thayaden
1119 posts
#1
This topic is linked to null - null.
Y by
Crazy Idea but $(M,\gcd )$ I think the condtions work

$$\gcd(3,7)=\gcd(7,3)$$and
$$\gcd(3,7)=\gcd(3,101)$$yet
$$7\neq101$$
This post has been edited 1 time. Last edited by Thayaden, Sep 18, 2024, 6:47 PM
Z K Y
G
H
=
a