you should think of the projective case as like "adding points at infinity" to the affine case
#elementary-number-theory
torn escarp
a more clear example is look at a hyperbola like $x^2-y^2=1$ then when you make it homogeneous you end up with $x^2-y^2=z^2$ now you can do something you couldn't do before and look t when $z=0$ and you end up with $x^2-y^2=0$ which gets you $x=y$ and $x=-y$ as solutions which correspond to the asymptotes
sterile pumiceBOT
Merosity
torn escarp
although when working in the projective case your points are really equivalence classes
so we effectively added on the points (x,y,z) that are (1,1,0) and (1,-1,0)
sacred junco
although when working in the projective case your points are really equivalence ...
although when working in the projective case your points are really equivalence classes
can you explain this bit in general ?
torn escarp
any point you have (x,y,z) = (kx,ky,kz) for k nonzero
you can see this as a consequence of doing that substitution earlier in a way, if you pick k=1/z
then you reclaim your original affine curve (x,y,1)
well I should say (X,Y,1) because I cheated and should have put (x/z, y/z, 1)
but X=x/z and Y=y/z are your variables now, hopefully I'm not confusing
sacred junco
not confusing
torn escarp
but this gives you a way to partition now into two distinct sets, when z=0 and z=1 effectively
the z=0 are your new points at infinity
torn escarp
and you can actually keep going down the chain
look at when y=1 and y=0
so that your projective space is just a union of a bunch of affine spaces
sacred junco
hello!
are you good with advanced probability?
#probability-statistics maybe ?
everyone is ignoring me
sacred junco
@torn escarp sorry to ping you but is there a book to read about that stuff ? The text i am reading doesn't explain it (basically writes it off in the overview chapter) .
inner anchor
i think in tate-silverman there is an appendix on the projective plane
left sigil
I second the appendix in Silverman and Tate (and also the rest of that book; I'm going through it now and it's an absolute blast). Doing a brief search in Springer, the first books that I can find entirely on projective geometry are both from the late 1980s (H.S.M. Coxeter in 1987 and Pierre Samuel in 1988) and so might be outdated, but their descriptions do at least claim to be introductory. @sacred junco
sacred junco
sounds good , i tried silverman's appendix which was super intuitive to read and for now matches my needs . Thanks for the suggestions , i might look into them !
sterile pumiceBOT
You don't have the selfroles Advanced, do you want to add them? (y(es)/n(o))
(Tip: use ,iam to add roles without this prompt.)
modern kestrel
hey just wondering would p=5 disprove this https://gyazo.com/eacdeba52c871a614c8902656a5a561c
bleak musk
hey just wondering would p=5 disprove this https://gyazo.com/eacdeba52c871a614c8...
Yep! the only i such that 2 <= i <= p - 2 are i = 2 and i = 3, both of which square to -1 (mod 5)
sacred junco
Has anyone seen a formula looking like this? $$N^2 = 1 + 1 + 2 + 2 + ... + (N - 1) + (N - 1) + N$$
sterile pumiceBOT
Lavonu
sacred junco
I see
inner anchor
contradiction works for the first direction
also if you know/are allowed to use the fact that a number a is a quadratic residue mod p iff a^((p-1)/2) is equal to 1 then the problem becomes pretty easy
plain vault
yeah i didn't think i could, or i thought i could only build off of q1
i think i struggled to formalize the contradiction
i.e. i assume -x mod p is a quadratic residue, then there exists y such that y^2 = -x mod p
broke that down into y^2 = -1 * x mod p
and we know that -1 mod p is not a quadratic residue
not too confident about how to conclude here that x mod p must not be a quadratic residue either
inner anchor
so basically you need to prove that the product of a nonresidue and a residue cant be a residue
so if x is a quadratic residue, then x = t^2, and so -1 = (y/t)^2, which is a contradiction
the other direction should be pretty similar
plain vault
ohhh got it thank you!
inner anchor
cool and good
vital hill
i'm trying to use this rule but it seems to not be holding
is there some kind of condition that needs to hold before i can use it
sterile pumiceBOT
vital hill
i thought if we multiply it together once i would get 15
so we have to mod it again
to get to 15
haughty lichen
yes
vital hill
hmm ok
sleek cove
its the for me 😼
solemn bramble
so we have to mod it again
I think ... if you think of "mod" as an action, it feels weird. But if you think — 45 just IS 15 in the "mod 30" world, it's less weird.
tired rampart
Is there any "pretty" way of doing this, without needing 9 for loops?
tired rampart
<@&286206848099549185>
sacred junco
I don't have a pretty way but I think I can improve the computation time
the desired positive integer exceeds 10^9 and is 0 mod 10
barren herald
$\forall x \in \mathbb{N}* -{1} : x(x-1)(x+1) $ can't be a cube.
bleak robin
How would I solve; $a^2 - 24a + 36 = n^2 (mod p)$, solving for odd primes p.
sterile pumiceBOT
ohNoiAmHere
bleak robin
is it just completing the square?
leaden swan
(a-6)^2-n^2=0 mod p
Now just factorise
(a-6-n)(a-6+n)=0 mod p
Implies a-6-n=0 mod p or
a-6+n=0 mod p
bleak robin
but isnt (a-6)^2 = a^2 - 12a + 36, what do i do with the other 12a?
bleak robin
oh lol, yea i cant factor the polynomial; thats where im confused
bleak robin
can i do (a/2 - 3)^2 = n^2 (mod p), theta = n^2 (mod p) and then use legendre?
bleak robin
how can i order {-7, -6, ..., 8} into two sets such that their sums, sums of squares and sum of cubes are all equal?
bleak robin
of equal size
chrome bluff
Is -8 not in this set?
sage fern
-7, -6, ... 8 is 16 numbers because of 0
ok so firstly what are the totals, bc you divide those by two to get the sum of each set
uhhhh
8, 344, 512, makes sense
uhhh wonder if you can do something with modulo something
4, 172, 256 are our subtotals
something about the cubes mod 8? i'm semibusy rn
bleak robin
yea i have that but am just confused how to partition it
the other thing that i have is that if you add or subtract n from all the numbers then they will still satisfy the property
but i dont know the best place to look at it from
wise oyster
the other thing that i have is that if you add or subtract n from all the number...
well if that's true then if you take the fact that the squares have to be equal, if you expand all of the new squares where youve subtracted n in both sets youll get the original sum of squares which we required to be equal, 8n^2 which we can therefore cancel out, and -2n(sum of numbers) which can therefore also be cancelled out so that condition doesnt change anything
cause the same thing will happen with the cubes
if they have the property of sums, square sums, and cube sums being the same that property will also hold for the n being subtracted (or added)
so you can probably use that property to instead talk about a nicer/easier set of numbers?
cause if you consider any set of 16 consecutive numbers and split it in two like you said then you can just subtract a relevant constant from everything at the end to get what you originally wanted
oh consider this: $3(a^2 + b^2)(a+b)=(a+b)^3 + 2(a^3 + b^3)$ If $a,b$ are in one set and you consider doing the same operation with $c,d$ from the other (assuming this was a problem with 4 elements) then it would show you that equality of sum of cubes comes from equality of sum of squares and regular sum. Im pretty sure this is also true of your problem with 16 elements, just a more tedious expansion
sterile pumiceBOT
Little Narwhal
wise oyster
nvm it doesnt extend to bigger sets
okay so i found it
but sort of by trial and correction
it came from two observations, that 64 + 8 =72 (8^2 + 2^2 + 2^2 = 6^2 + 6^2) and that 7^3+1-5^3-3^3+4^3 = 256 = (1/2) * 8^3
but yeah i kind of came across those by trial and correction
probably a more elegant way to do this
bleak robin
ok thank you
sacred junco
Hey how do I do 2c? I know the solution is 1, 2, 3, 4, 6 or 12
i know its not 1 2 or 3 unless y3 = -1 (mod 7) is fine and theres a typo
bleak robin
Use Lagrange
sacred junco
so ive come across this.. seems like an expanse of 4 digits seems common
4 digits aka 4 zeroes
aside from 11 and 23 i havent tried other sets of numbers
there might be others where each end is a prime such as this where 11 and 23 are primes
dont know about anything definitive about this but sure seems like there is something special here
124 was the next one
https://www.numberempire.com/primenumbers.php
i used this which goes to 128 digits
seems to be grouped like this?
sacred junco
17 __ 29
does not start at 0..
1 2 5 26
I haven't gone further yet but i wonder if a relation to 4 will pop up
sacred junco
prime A zeroes prime B = prime C
rigid tusk
it was answered when #advanced-number-theory but I still dont really get it
so it is suffice to show that 70 divides at least one of 10 or 14 or 35
but what about 2, 5 and 7?
do they work?
i am just confused so if you can explain it for my brain that would be great
gentle lily
Prove that there exists a positive integer $N$ such that there are at least 2005 ordered pairs $(x,y),$ of non-negative integers $x$ and $y,$ satisfying $x^2 + y^2 = N.$
sterile pumiceBOT
LifeSource
gentle lily
Suppose $N = n^2$, for $n \in \mathbb{Z}^+$. Then, consider the parametrization of all possible values values of $x$ and $y$:
$$\begin{cases} x = 2 k_0 n_1 m_1 \ y = k_0 (n_1^2 - m_1^2) \ n^2 = k_0 (n_1^2 + m_1^2) \end{cases},$$
for $k_0 \in \mathbb{Z}^+$, $n_1,m_1 \in \mathbb{Z}^+ \cup {0 }$, and $\text{gcd}(n_1,m_1) = 1$. Now, take $k_0 = k_1^2$. Focusing on our equation for $n^2$, we get
$$n^2 = k_1^2 (n_1^2 + m_1^2) = (k_1 n_1)^2 + (k_1 m_1)^2.$$
Thus, we have created another Pythagorean identity. Furthermore, we can continue our parameterization as such:
$$\begin{cases} k_1 n_1 = 2 k_2^2 n_2 m_2 \ k_1 m_1 = k_2^2 (n_2^2 - m_2^2) \ n^2 = k_2^2(n_2^2 + m_2^2) \end{cases},$$
where we take the constant that scales our parameterization to be another perfect square ($k_2^2$). Notice that we can continue this process as many times as we wish, each of the following form:
$$N = n^2 = (k_i n_i)^2 + (k_i m_i)^2,$$
for positive integers $k_i$ and nonnegative integers $n_i,m_i$.
sterile pumiceBOT
LifeSource
gentle lily
So here is what I have so far for the problem above
I am not sure if I still need to prove uniqueness of the triples.
gentle lily
<@&286206848099549185>
gentle lily
Anyone?
fluid shard
https://cdn.discordapp.com/attachments/496785853180543027/834555700670627880/unk...
Are you still confused about this?
rigid tusk
Are you still confused about this?
oh yea
fluid shard
So $(\mathbb{Z}/71\mathbb{Z})^\times$ has order 70, right?
sterile pumiceBOT
¯\_(ツ)_/¯
fluid shard
Oh shoot, I just realized that I'm also a bit confused on this
I'll have to get back to you if I figure it out
Sorry 😬
Ohhhhhhhhh, no I got it
Cool cool cool
Okay so the order of 2 has to divide 70
Which implies that $\text{ord}(2) \in {1,2,5,7,10,14,35,70}$
sterile pumiceBOT
¯\_(ツ)_/¯
rigid tusk
@fluid shard so any of those numbers in the set works?
fluid shard
Not quite, you need to pick 3 of them so that the only possible option is that the order of 2 is 70
If you pick a=2, b=5, c=7 then there's still a chance that 2 has order 14
But, for example, if you check that $2^{35} \neq 1$, then you know that $\text{ord}(2) \neq 5,7, \text{or }35$
sterile pumiceBOT
¯\_(ツ)_/¯
rigid tusk
and if i check that 2^10 !=1 then ord(2) !=2 5 or 10
fluid shard
Exactly
So you just need that last number, because checking 10 and 35 eliminates 1,2,5,7,10, and 35
fluid shard
Yep!
inner anchor
Suppose $N = n^2$, for $n \in \mathbb{Z}^+$. Then, consider the parametrization ...
i dont really understand what you are doing or how what you are doing generates new triples
have you proven that for any square there exist arbitrarily many representations as a sum of two squares
grave carbon
Im having some trouble on the inductive step, so I’d like some help pls
sterile pumiceBOT
beeswax
inner anchor
Use the identity $x^n -1 = \prod_{d |n} \Phi_d(x)$
sterile pumiceBOT
Pappa
inner anchor
specifically look at $x^{2n} -1 = \prod_{d |2n} \Phi_d(x)$
sterile pumiceBOT
Pappa
inner anchor
this is infact a corollary of a more general statement that says that if $p\nmid n$ for a prime p, then $\Phi_{pn} (x) = \frac{\Phi_n (x^p)}{\Phi_n(x)}$
sterile pumiceBOT
Pappa
inner anchor
proof is just to note that the degrees of both sides are the same and then just show that every root of the LHS is a root of the RHS
grave carbon
specifically look at $x^{2n} -1 = \prod_{d |2n} \Phi_d(x)$
Is this heading towards
$$ \prod_{d |2n} \Phi_d(x) = \prod_{d |n} \Phi_d(-x)$$ from the inductive hypothesis?
sterile pumiceBOT
beeswax
inner anchor
what do you mean
grave carbon
Wait nvm, what I just sent doesn't exactly move me towards a direction
inner anchor
**Pappa**
the idea here is just to simplify the RHS so that you can use the induction hypothesis
to split the product into parts where on one of the parts you can simplify using the induction hypothesis
ebon yacht
it has p-1 order
nope any Z/nZ has order n 0 is still in the ring/field
dusty bough
so, i was told this is lagrange's theorem, however looking online it doesn't seem to match with the other definitions of it, am i just not understanding it?
leaden swan
That's definitely not lagrange
grave carbon
Any hints as to how I can prove the 2nd and 3rd case? I tried out some values, and that’s the formula I came up with
sterile pumiceBOT
beeswax
leaden swan
Maybe the fact that (1-e^(2ix))=-2i sinx e^ix is useful
inner anchor
prove a lemma, that if $p|n$ then $\Phi_{pn} (x) = \Phi_n (x^p)$
sterile pumiceBOT
Pappa
inner anchor
this is basically saying that a is a pn:th primitive root of unity if and only if a^p is a nth primitive root of unity
young grotto
Any hints for reducing 2^127-1 (which we know is prime) modulo 2^31+1?
fervent crest
2^31=-1
young grotto
yes of course. thank you
sonic urchin
nope any Z/nZ has order n 0 is still in the ring/field
They're taking the multiplicative group
rain mountain
yea
grave carbon
I wrote up this proof, and i was wondering how I would show $\Phi_n(x)$ and $x^n\Phi(\frac{1}{ x})$ have the same roots
sterile pumiceBOT
beeswax
mild siren
Oh, they’re the same polynomial
How are you comparing the coefficients? The argument you've given only demonstrates that one polynomial is the other one with the coefficients reversed, then asserted that the coefficients of the same power of x must be the same. In particular, you have used no properties of Phi(x) other than it is a polynomial.
You should think about what the roots of Phi_N(x) are, and then think about what inputs would make Phi_N(1/x)=0.
grave carbon
Thank you, I will work with this hint
tawdry root
Hi
Can anyone explain a Number theory Congruence question ?
I get that the mouse moves 5 hours in a day... but what does the question mean by 'passing through 25mins on the clock'?
chrome bluff
I'm not sure where the 5x came from
tawdry root
I'm not sure where the 5x came from
It travels 5 hours in a day and x represents the no. of days
we have to find when the remainder will be 4
chrome bluff
Ah the 25 minute thing, I follow
tawdry root
Ah the 25 minute thing, I follow
even you didn't get that thing?
chrome bluff
I get that the mouse moves 5 hours in a day... but what does the question mean b...
It's a very literal problem. The mouse is traveling a total of 25 minutes on a clock each day. On the clock, each minute is represented by a tick. So they travel a total of 25 ticks
chrome bluff
even you didn't get that thing?
This problem is weirdly worded
tawdry root
It's a very literal problem. The mouse is traveling a total of 25 minutes on a c...
But how does it move 5 hrs a day when he is moving 25mins a day
chrome bluff
What I don't understand here is how 25x simplified to x from this. It is true that 20mod12 is congruent to 8mod12, but where did the 25 go?
Also, please stop pinging me.
You're going a little crazy with that
tawdry root
Also, please stop pinging me.
ohh sorry😅
chrome bluff
....
chrome bluff
ohh sorry😅
This is a reply with no ping
<@&286206848099549185> can someone help me figure out what's going on with their problem? In the last line, how does it simplify to x cong. 8 mod 12? I get the 8 mod 12, but where did the 25 go?
tawdry root
i solved 5x = 4 mod 12 by just finding a multiple of 5 which is 4 more than a multiple of 12
40 worked fine 5x=40, x=8 ans
chrome bluff
That logic makes sense
sacred junco
that is a very bad intro to modular arithmetic nontheless
chrome bluff
I agree...
slim agate
25 \equiv 1 mod 12
haughty lichen
indeed
wise oyster
@chrome bluff 25 congruent to 1 mod 12 and 20 is congruent to 8 mod 12
A better way to go about it than multiplying by 5 without motivation is to note that the inverse of 5 mod 12 is 5, which explains multiplying by it so we get x congruent to something mod 12
dusty bough
$2^{k+1} + 1 \equiv 2 + 1 \equiv 0 (\mod 3)$
sterile pumiceBOT
moment
dusty bough
how does this uh work?
maybe a stupid question but im still trying to grasp the concept of modular arithmetic properly
torn escarp
there's missing info or it's incorrect
sacred junco
it's not true for all k
dusty bough
uh $k \in \bN$
sterile pumiceBOT
moment
torn escarp
have you heard of fermat's little theorem or euler's theorem yet @dusty bough
dusty bough
yes
torn escarp
you should list out on paper 2, 2^2, 2^3, 2^4, 2^5 all mod 3 and see what pattern you get
dusty bough
oof i wrote down the wrong expression from memory, here's the one that i wanted to write:
$2^{8k + 3} - 2^{4k+2} + 1 \equiv 8 -4+ 1 \equiv 0(mod 5)$
so i get that we're writing it as 2^3 * 2^8k and 2^2 * 2^4k but what happens after that
how do we go from that to \equiv 8 - 4 + 1
sterile pumiceBOT
moment
torn escarp
since this is mod 5 that means if x is nonzero, x^4 = 1 mod 5 by fermat's little theorem right
dusty bough
yes
torn escarp
in general when you're working mod p you should look for p-1 in the exponent to simplify things to 1 like this
so you start separating it out with exponent rules, look at the individual term
$2^{8k+3}$ just try to simplify this single term mod 5
sterile pumiceBOT
Merosity
torn escarp
one way is you can write $(2^4)^{2k} * 2^3 \equiv 1^{2k} *2^3 \equiv 1 *8 \mod 5$
sterile pumiceBOT
Merosity
torn escarp
you're welcome
slim agate
You probably mean f(2^n) = n
modern kestrel
okay cuz that would be mapping 2^n to n?
proving injectivity for that should be really ez right
since its just f(2^a )= f(2^b ) = a = b
and when a = b, f(2^a) = b which should prove surjectivity meaning it is bijective
is that the correct logic?
grave carbon
How can I prove the implication
$$ p^k = \Phi_p(1) \cdots \Phi_{p^k}(1) \implies \Phi_{p^k}(1) = p?? $$
mild siren
So, now I'm just trying to close that gap
Induction
torn escarp
you could divide directly the k-1 eqn from the k eqn
grave carbon
you could divide directly the k-1 eqn from the k eqn
What do u mean
torn escarp
$$\frac{p^k}{p^{k-1}} = \frac{\Phi_1(1)\cdots \Phi_{p^{k-1}}(1)\Phi_{p^k}(1)}{\Phi_1(1)\cdots \Phi_{p^{k-1}}(1)}$$
sterile pumiceBOT
Merosity
torn escarp
nearly everything cancels
terse acorn
Any hints for this one? I am not very good with Legendre symbols...
torn escarp
try using the fact that if a=b mod p then (a/p)=(b/p)
sacred junco
sterile pumiceBOT
beeswax
grave carbon
Nvm, it's not
inner anchor
the easy generalization of the legendre symbol is the jacobi symbol
but it isnt quite as nice
grave carbon
the easy generalization of the legendre symbol is the jacobi symbol
I see
Also, 1 more question:
grave carbon
For this, I’m having a little trouble proving the reciprocity rule
inner anchor
is this the jacobi symbol or
grave carbon
is this the jacobi symbol or
yes
inner anchor
hmm
so we want to use the standard version of quadratic reciprocity
also we know that the jacobi symbol is multiplicative
so i think a sort of pairing argument should work
writing out $a = p^{\alpha_1}_1 \ldots p^{\alpha_n}_n$ and $c = q^{\gamma_1}_1 \ldots q^{\gamma_m}_m$
sterile pumiceBOT
Pappa
grave carbon
Prime factors of a not in prime factors of c, right
inner anchor
they are coprime
so their prime factors are distinct
unless i misunderstood what you meant
inner anchor
epic
now we have $\left(\frac{a}{c}\right)\left(\frac{c}{a}\right) = \left(\frac{p^{\alpha_1}_1 \ldots p^{\alpha_n}_n}{q^{\gamma_1}_1 \ldots q^{\gamma_m}_m}\right) \left(\frac{q^{\gamma_1}_1 \ldots q^{\gamma_m}_m}{p^{\alpha_1}_1 \ldots p^{\alpha_n}_n}\right)$
sterile pumiceBOT
Pappa
inner anchor
damn this is a mess to latex lol
inner anchor
yee
grave carbon
Ty
inner anchor
np
grave carbon
So far, it's correct right?
Not quite sure how to close it to the equality the problem asked for
inner anchor
im not sure the last equality is correct
grave carbon
im not sure the last equality is correct
But was that what u meant by pairing
inner anchor
yes
but we need quadratic reciprocity for powers of primes
ill have to think this through again
oh wait
i slightly scuffed up the defn of the jacobi symbol
or wait
by the defn we know that $\left(\frac{p^{\alpha_1}_1 \ldots p^{\alpha_n}_n}{q^{\gamma_1}_1 \ldots q^{\gamma_m}_m}\right) \left(\frac{q^{\gamma_1}_1 \ldots q^{\gamma_m}_m}{p^{\alpha_1}_1 \ldots p^{\alpha_n}_n}\right) = \left(\frac{p_1^{\alpha_1}}{q_1}\right)^{\beta_1} \left(\frac{q_1^{\beta_1}}{p_1}\right)^{\alpha_1} \ldots$
sterile pumiceBOT
Pappa
inner anchor
and then you can use the complete multiplicativity of the legendre symbol to get that $\left(\frac{p_1^{\alpha_1}}{q_1}\right)^{\beta_1} \left(\frac{q_1^{\beta_1}}{p_1}\right)^{\alpha_1} \ldots = \left(\frac{p_1}{q_1}\right)^{\alpha_1 \beta_1} \left(\frac{q_1}{p_1}\right)^{\beta_1 \alpha_1}$
sterile pumiceBOT
Pappa
sterile pumiceBOT
beeswax
grave carbon
Oh disregard
bleak edge
I suspect that this might be better for [#groups-rings-fields](/guild/268882317391429632/channel/496784958430380033/) or even [#advanced-number-theory](/guild/268882317391429632/channel/496785853180543027/), but I came across this in a project for my elementary class so I'll ask it here. I know that $(\mathcal{A}, +, *)$ is a UFD, and so I've been trying to find it's irreducibles, but I'm really struggling to do so. Does anyone know how to find them?
sterile pumiceBOT
tox
mild siren
I suspect that this might be better for \<#496784958430380033> or even \<#496785...
What is the set A you want here?
sterile pumiceBOT
tox
torn escarp
@bleak edge if I give you f, what conditions do you need to put on it to be invertible?
that will tell you what your units are
and that also tells you what things that are not units would have to look like too
bleak edge
Yeah, it's invertible if f(1) = 1
But when I try $f(n) = n-1$ but then as far as I can tell $(f)$ is just all non-units
sterile pumiceBOT
tox
mild siren
Yeah, it's invertible if f(1) = 1
I claim that it's actually enough that f(1) is not 0 for f to be a unit. That tells you that in order for something to be irreducible, it must at least be zero at zero. This gives rise to the natural question, what is the first nonzero number?
So you might think about if f's first nonzero element is f(a) and g's first nonzero entry is g(b), what is the first nonzero term of f*g? (this should depend on the prime decomposition of a and b, since multiplication is determined by divisibility of the arguments)
This line of reasoning can help try to find some of the irreducibles
Though do be aware that meaningfully identifying all irreducibles isn't necessarily tractable.
bleak edge
I thought that a unit is just any element with an inverse? I'm not sure I follow why it must be the case that f(0) = 0? Actually it occurs to me I don't know how (f*g)(0) is defined? Are we considering 0 to be the only divisor of 0? Is it f(0)g(0)?
mild siren
Sorry, you're right, f(1)=0 are the nonunits
What I said still stands, just index from 1
torn escarp
for g to be an inverse to f we need $(fg)(1)=1$ and for $n>1$ you need $(fg)(n)=0$. So first condition is simple, $f(1)g(1)=1$ means we need $f(1)$ to be nonzero. Then we can look at $$0 = (f*g)(n)=\sum_{d|n} f(d)g(n/d) = f(1)g(n)+\sum_{d|n, d\ne 1} f(d)g(n/d)$$ then rearrange for a nice recursive formula for the inverse $$g(n) = \frac{-1}{f(1)} \sum_{d|n, d\ne 1}f(d)g(n/d)$$
sterile pumiceBOT
Merosity
torn escarp
I suppose there's some wiggle room in your original question depending on how you define 'arithmetic function'
if that requires it to be multiplicative or completely multiplicative then the condition f(1)=0 actually forces f(n)=f(1*n)=f(1)f(n)=0
I guess next thing to try to do would be, given f(1)=h(1)=0 with f arbitrary, what are the possible invertible g we can use to write f*g = h? that would be enough to distinguish the elements that are in the same equivalence class
maybe something similar can be done with defining some recurrence relation on g
sterile pumiceBOT
ryane
sacred junco
valid notation for what?
linear in what sense
this notation makes sense to me as long as n is not 0 so that the inner sum is a finite one
im assuming this is over the integers
or naturals
what you wrote is a infinite series that diverges, you probably want to consider a function $f(k) = \sum_{n=1}^k \sum_{d^2 | n} d$
sonic urchin
This is true but doesn't show linearity
You can bound the inner sum by √n, and then the overall thing will be bounded by summation √n which is of order x^{3/2}
oh wait I was taking summand to be 1
sacred junco
yea if the summand was one that would work even for summing over d|n
torn escarp
I played around with a lambert series for a few minutes to get an upper bound but the upper bound is not linear, it's n^{5/2} sadly, unless I made a mistake
first I rewrite $\bar \tau(n) = \tau(n) \mod 2$ since it's 1 when n is a perfect square, 0 otherwise so that I could write the formula as $\sum_{d|n}\bar \tau(d) d$ which then can simplify in this crude inequality:
$$\sum_{n=1}^N \left( \sum_{d|n} f(d) \right) x^n \le \sum_{n=1}^N f(n) \frac{x^{n(n+1)}-x^n}{x^n-1}$$
sterile pumiceBOT
Merosity
torn escarp
it ends up simplifying quite nicely to an upper bound of $N \frac{2 \lfloor \sqrt{N}\rfloor^3+ 3\lfloor \sqrt{N}\rfloor^2+\lfloor \sqrt{N}\rfloor}{6}$
sterile pumiceBOT
Merosity
torn escarp
oh I end up getting that by putting $f(n) = \bar \tau (n) n$ and $x=1$ in the inequality
sterile pumiceBOT
Merosity
sleek cove
do you know Q is countable
upbeat wren
If anyone is interested: Let N be a square number. N ends in digits "XYZ". No square ends in "XYZ" + 2 nor "XYZ" + 6
Example: 625 x 625 ends in 625. No square ends in 627 (duh, no squares end in 7) nor 631.
torn escarp
if N is a square then it's congruent to 0 or 1 mod 4, so adding 2 or 6, which are equivalent mod 4 corresponds to getting a number that's 2 or 3 mod 4 @upbeat wren
so you could generalize your rule to taking a square and adding any number that has remainder 2 when divided by 4, not just 2 and 6
I guess technically to align with what you're saying I should walk through the same reasoning mod 8 since by the chinese remainder theorem we can think of the last 3 digits as looking mod 10^3 which splits into 2^3 and 5^3
upbeat wren
bingo!
meager pond
Is there a modular arithmetic way to find all the integer solutions to $m^2 = n^3 + 252$ ? (I know what the solutions are but can't prove that none others exist)
sterile pumiceBOT
Frosty
proper oyster
maybe you can split the equation to $m^2 - 225 = n^3 + 27$ and then play on the divisors by factorising both sides (don't know if that works tho, just an idea)
sterile pumiceBOT
Extends
meager pond
m = +/- 15 and n = -3 is a solution but factorising both sides doesn't seem to lead anywhere
proper oyster
well it leads to this solution at least
meager pond
Yes, there are 4 more solutions like that but I can't prove that none others exist
proper oyster
I don't actually think it's solvable through modular arithmetic, you might have to get your hands dirty by working with elliptic curves and/or quadratic integers i think
You can find solutions by adding / removing squares and cubics from both sides but it won't give you that this are the only solutions as far as I know
meager pond
I was starting to think so too, thanks for trying though!
Yes, everything online seems to be about factorising over some structure
proper oyster
yeah, I think #advanced-number-theory is better for that kind of problem (see mordell curves to get some info about that type of equations if you want!)
meager pond
I only know basic number theory so I doubt I'll be able to understand much of the methods, that was just a side problem that I was given
sterile pumiceBOT
Ionescu Emi-Marian A6
magic egret
why if $3 | n$ then $7 | 93^n - 93 +1$ ?
sterile pumiceBOT
Ionescu Emi-Marian A6
inner anchor
$93^n - 93 +1 \equiv 2^n -2 +1 \equiv 2^n -1 \pmod{7}$
sterile pumiceBOT
Pappa
inner anchor
now try to use the fact that $3|n$ to show that $2^n \equiv 1 \pmod{7}$
sterile pumiceBOT
Pappa
magic egret
$3 | n$ so n=3m $(2^3)^m mod 7 \equiv 1^m mod 7$
sterile pumiceBOT
Ionescu Emi-Marian A6
magic egret
if $n \equiv 0 \pmod{n_1 \cdot n_2 ... \cdot n_k}$ iff n is divisible by $n_1 , n_2 , ... , n_k$ then is there an modular equation that says n is divisible by at least one of ${ n_1 , n_2 , ... , n_k }$ ?
sleek cove
is p a prime
magic egret
no
sterile pumiceBOT
Ionescu Emi-Marian A6
magic egret
yes
in other words are there functions f,g such that
$f(n) \equiv 0 \mod g( n_1 , n_2 , n_3 , ... , n_k)$ is true iff n is divisible by an $n_i$
sterile pumiceBOT
Ionescu Emi-Marian A6
leaden swan
f(n)=n,g(n_1,n_2...)=n_1 works I think
magic egret
i want $f(n) \equiv 0 \mod g( n_1 , n_2 , n_3 , ... , n_k)$ to be true iff there exists an $n_i$ from ${n_1 , n_2 , ... , n_k }$ such that $n \equiv 0 \mod n_i$
sterile pumiceBOT
Ionescu Emi-Marian A6
magic egret
for g(n_1,n_2,...) = n_1 it would be true iff n is divisible by n_1 which is not what i want
magic egret
then it would be true iff for all $n_i$ from ${n_1 , n_2 , ... , n_k }$ $n \equiv 0 \mod n_i$
sterile pumiceBOT
Ionescu Emi-Marian A6
magic egret
and i want the equation to be true iff for at least one of ${n_1 , n_2 , ... , n_k }$ $n \equiv 0 \mod n_i$
sterile pumiceBOT
Ionescu Emi-Marian A6
proper sleet
What is an analogue of a characteristic of a ring for an algebraic structure S for which using 1 in a sum n times is undefined instead of giving 0?
sacred junco
what are 1 and 0 in an algebraic structure S?
proper sleet
I'm trying to compare row spaces of two integer matrices with equal width. If you consider two row vectors v1 and v2, they have equal number of coordinates. You can perform vector addition of v1 and v2, can scale any of them by an integer. Set of all possible sums of v1 and v2 with different coefficients (weights) is called a linear span of a set of vectors. All these sums [and their evaluated values] are called linear combinations. You can consider a lexicographic order on vectors (like that on strings, but there can be infinitely many elements).
I want to find the smallest (in the lexicographical sense) vector which comes after zero vector.
And then "traverse" this "dense" (in unusual sense) set and prove of refute equality of row space as if by induction in both directions (proving/refuting in one direction would suffice because for each positive linear combination there is one with the same absolute value but different sign).
You can consider each such vector as a vector of ordinals (the smaller the coordinate in the vector, the smaller the corresponding coordinate in the vector from "sparse" (in unusual sense) set.
It can be impossible to increase the right-most coordinate of vector from the "sparse" set without changing the numbers on the left. So "traversal" is like incrementing the numeral. But there is no fixed base and it can even be infinite.
@sacred junco That's basically what I'm trying to describe.
"sparse" set is the set of all linear combinations
"dense" set is the set of vectors that is being traversed and is isomorphic to the "sparse" set.
1 and 0 in the definition of characteristic of a ring are multiplicative and additive identities. Honestly, Idk how to better model these algebraic structures.
median vale
today i found the largest prime in the world
median vale
wanna know how to find it?
leaden swan
Yes
median vale
take every single prime number we already know
then add one to it
now it is not divisible by every single prime smaller than it
meaning it is prime
now break in to a bank i guess
haughty lichen
Well it could be divisible by some prime numbers between your number and largest known prime and therefore not be a prime
median vale
Well it could be divisible by some prime numbers between your number and largest...
i couldnt
let us say a smaller example
2 x 3 x 5 x 7
- 1
211
haughty lichen
Sorry to break your bubble but that isn’t always true
median vale
Sorry to break your bubble but that isn’t always true
counter?
haughty lichen
2 * 3 * 5 * 7 * 11 * 13 +1
haughty lichen
The argument was different
median vale
by taking all of their product and adding one
sage fern
bruh
haughty lichen
It said all products of primes + 1 had new prime factors
median vale
ergo finding the largest prime known
sage fern
you don't find it
haughty lichen
Not that that the new number was a prime
median vale
It said all products of primes + 1 had new prime factors
ooo
median vale
the only reason it exists is to say there are infinite primes
sage fern
yes
median vale
yea
jolly echo
@near pendant hi.
sleek cove
hi @near pendant
near pendant
@jolly echo hi.
@sleek cove Hi.
What's up my gs
I'm pretty crap at number theory lmao why this channel
grave carbon
If $k$ is a positive integer, I was wondering if someone can show/explain why
$$ (kn+k)! = (kn+k)(kn+k-1) \cdots (kn+1)(kn)! $$
sterile pumiceBOT
beeswax
grave carbon
Not sure where the (kn+1) is coming from
sacred junco
it's the same thing as writing, say, 10!, as 10⋅9⋅8⋅7!
grave carbon
$(kn+k)(kn+k-1)(kn+k-2)\cdots(kn+k-k)!$
Why is the (kn+1) there?
sterile pumiceBOT
beeswax
sonic urchin
$(kn+k)(kn+k-1)(kn+k-2)\cdots(kn+k-k)!$
Why is the (kn+1) there?
kn+1 = kn+k-(k-1)
I think you're just confusing the order of terms
grave carbon
kn+1 = kn+k-(k-1)
So, you're claiming
$$(kn+k)! = (kn+k)(kn+k-1) \cdots (kn)(kn+1)! $$
sterile pumiceBOT
beeswax
sonic urchin
No
kn+1 will come before kn
Because this sequence is decreasing
And factorial will be on kn
sonic urchin
I think you're just confusing the order of terms
That's what I meant
torn escarp
2 | (1+3) but 2|1 and 2|3 is false
deft pulsar
ah... makes sense...
torn escarp
the other way around is true though
deft pulsar
so if I understand correctly this is mostly due to the fact that two positive integers are coprime
torn escarp
yeah that's a good way of thinking about it
either b and c are both divisible by a, or they're both not divisible by a
try to prove that
torn escarp
I don't understand what you've written but you should have something where you reason through where one is divisible by a and the other isn't
suppose a|b but not c, then by writing it as ma=b+c then subtract ma-b=c but since a,b are divisible by a, then c must be: contradiction
deft pulsar
hm
if I add two those two cases I'll end up with four casework 
will think about that, thanks
torn escarp
sounds like too many cases, since you can pick b or c without loss of generality
and since I just showed they can't be different, then they must be the same, so there's nothing more to do really
sterile pumiceBOT
ryane
leaden swan
Can you send the para where you found that?
Here,I think it means a function in o(1)
You know big O?
ig
That's why I need more context
Well small o is different from big O
I think so
sterile pumiceBOT
ryane
leaden swan
If you take any function in o(1) and put it there,the expression is true
Yes
Ok,f(x)=1 doesn't work
Here it means any function that eventually becomes zero
Should work,ig
verbal cedar
For integers $a,b,c,d,\delta$, if $a^2+b^2$ and $c^2+d^2$ are both divisible by $\delta$, will both $ad-bc$ and $ac+bd$ also be divisible by $\delta$?
sterile pumiceBOT
nix
verbal cedar
I found that $(a^2+b^2)(c^2+d^2)=(ad-bc)^2+(ac+bd)^2$
sterile pumiceBOT
nix
verbal cedar
so the sum of the squares is divisible by delta^2, but I dont know where to go from there
torn escarp
5 = 1^2 + 2^2 so it's divisible by 5, but when we expand it out 5*5 you have 25 = 3^2 + 4^2 and neither 3 nor 4 are divisible by 5
verbal cedar
5 = 1^2 + 2^2 so it's divisible by 5, but when we expand it out 5*5 you have 25 ...
oh thats right i forgot delta is not 1. so i dont believe that case is possible.
the left side would have to be divisible by at least a prime squared
can i at least say that if one of them is divisible by delta, ad-bc for example, then the other ac+bd must be as well?
inner anchor
I found that $(a^2+b^2)(c^2+d^2)=(ad-bc)^2+(ac+bd)^2$
Dont you get that from this
Look at it mod delta
torn escarp
yeah, this kind of thing is not specific to this representation, if you have a=b+c and if a,b are divisible by delta, then c is divisible by delta
verbal cedar
okay cool. then maybe i can do proof by contradiction, supposing neither are divisible. either i find a contradiction proving it or show that it's false.
spare tangle
Hi, I just wanted to double-check my understanding here. 14 = 2 (mod 12) is the same as saying 2 = 14 mod 12, right? I also assume the congruency symbol should be used instead.
This is actually covered in my Computer Science module on Security, and I also wonder if the brackets notation is necessary as I've seen so before.
Please let me know if I've misunderstood this concept and also why we use this congruency symbol.
Shouldn't 2 = 14 mod 12?
Feel free to tag/mention/ping me if replying. Thank you ❤️
Just wanted to add, I have read a bit about the congruency symbol, and wanted to just double check if I've got this correct. Also, is it incorrect to use negative integers in relation to modulo arithmetic
sleek cove
2=14=2
acoustic tiger
Hi, I just wanted to double-check my understanding here. 14 = 2 (mod 12) is the ...
congruence is an equivalence relation so if a ~ b iff b ~ a. Technically you should use the congruence symbol, but sometimes people get lazy and just use the equal sign. And you can use any member of an equivalence class to represent the class, so negative numbers are fine and sometimes are more convenient than positive representatives.
spare tangle
congruence is an equivalence relation so if a ~ b iff b ~ a. Technically you sho...
Thank you. 🙂
sacred junco
How did i mess up on this gcd problem
sacred junco
Oh
tribal river
i need help pls someone teach me maths
weary gate
does anyone know how to implement this function:
f(1,2,1) = 3
f(1,2,2) = 5
f(1,2,3) = 8
f(1,2,4) = 13
f(2,6,1) = 8
f(2,6,2) = 14
f(2,6,3) = 22
f(2,6,4) = 36
terse acorn
I tried but couldn't get anything useful
leaden swan
For k=2 ,find a term which is prime(say prime is p)
Consider the subsequence (p,p+pq,p+2pq...)
Apply Dirichlet again to find a sequence of primes in (1,1+q,1+2q...)
terse acorn
Apply Dirichlet again to find a sequence of primes in (1,1+q,1+2q...)
Thanks, I will think about it
naive mist
sterile pumiceBOT
beeswax
leaden swan
irreducible as in prime?
Yea,Prime would work too in that case
Isn't the smallest element that is not one always irreducible
If that's your defn
grave carbon
Wait I forgot to add another condition to the problem
I'll just ask the question again, I'm so sorry
sterile pumiceBOT
beeswax
exotic plank
Quick question, does Legendre symbol =-1 imply primitive root ?
inner anchor
no right
given that the number of primitive roots is \phi(p-1) and the number of quadratic nonresidues is p-1/2
and by simple bounding $\phi(p-1) = \phi\left(\frac{p-1}{2}\right) < \frac{p-1}{2}$
sterile pumiceBOT
Pappa
inner anchor
if q = (p-1)/2 is a prime, there is only one nonresidue that is not a primitive root, that being 2q
or something like this
inner anchor
and by simple bounding $\phi(p-1) = \phi\left(\frac{p-1}{2}\right) < \frac{p-1}{...
oh here im assuming that the largest power of two dividing p-1 is 2
but it shouldnt matter
exotic plank
So to talk about Legendre symbol, it only concern about quadratic residues. ?
inner anchor
What do you mean
weary gate
hey
if you multiply odd numbers by powers of 2 you get an infinite chain of even integers that are divisible by the odd number (there are no collisions between integer chains )
frosty bough
so ive been doing this question
and in part b
idk how its jumped from modulo 19 to 18
hang on
i might hove found the thing im looking for
hidden amongst the lecture notes
yep no i found it nvm
ignore me
weary gate
anyone interested in working on something related to number theory?
so.
let's take the set of integers and modulate them into two sets using mod 2 on the position of the integer
you get two sets; one even and one odd
0,2,4,6,8,10,12,14,16,18,20,...
and
1,3,5,7,9,11,13,15,17,19,21,...
now, let's take those two sets and divide each of them by two using mod on the integer sets
you get 4 sets:
0,4,8,12,17,20,...
and
2,7,10,14,18,...
and
1,5,9,13,17,21,..
and
3,7,11,15,19,...
2,8,10,14,18,...**
any questions/input?
my theory is that there is a second power of odd and even where the modulator is 2^2 rather than 2^1
we'll look at the 2 sets that are even to 2^1 produced from modulating the first 2 sets we modulated into sets
0,4,8,12,17,20,...
and
2,6,10,14,18,...
as you can see the first set is even relative to 2^2
the second set is odd relative to 2^2
let's look a the odd sets now, the same rule applies
1,5,9,13,17,21,..
and
3,7,11,15,19,..
we see 9 and 21 are divisible by 3, rendering them even numbers relative to the odd set
(notice that the remaining integers in that set are prime numbers)
now, we look at the second set, and there are 2 even numbers relative to the first set, 3, and 15, both of which are first odd multiple (3) of the prime numbers in the set
let's expand these sets to see what we're doing
1 3 5 7 9 11 13 15 17 19 21 23 25 27 29 31 33 35 37 39 41 43 45 47 49 51 53 55 57 59 61 63 65 67 69 71 73 75 77 79 81 83 85 87 89 91 93 95 97
sec making a script to generate these integers
1 5 9 13 17 21 25 29 33 37 41 45 49 53 57 61 65 69 73 77 81 85 89 93 97
3 7 11 15 19 23 27 31 35 39 43 47 51 55 59 63 67 71 75 79 83 87 91 95
let's look at the first set for integers divisible by 3
inner anchor
these are just residue classes modulo 4
weary gate
9,21,33,45,57,69,81,93,...
notice that most of the remaining integers in that set are prime numbers
inner anchor
bruh
maybe looking up dirichlets theorem on arithmetic progressions is somewhat useful
my only other tip is to do some actual number theory to see that all of this can fit into a nice framework of theory
weary gate
this is new math that's all
weary gate
i think we can apply this theory to find all the prime numbers in the integer series
weary gate
i invented this field a few years ago
never researched dirichlet
if you have any insight/input let me know instead of dropping references/names
inner anchor
...
weary gate
look at these two sets
1 5 9 13 17 21 25 29 33 37 41 45 49 53 57 61 65 69 73 77 81 85 89 93 97
3 7 11 15 19 23 27 31 35 39 43 47 51 55 59 63 67 71 75 79 83 87 91 95
inner anchor
i simply suggest you learn what has been done before by mathematicians much greater than you and me
so that you dont have to retrace their steps in worse manner
weary gate
i'm not retracing steps
inner anchor
why are you so convinced this is novel
weary gate
it's not relevant
what's relevant is that we can make progress in this field without using references to things that have already been done
weary gate
my goal for today is to come up with a formula that finds all the prime numbers
weary gate
yes
inner anchor
yeah im out
weary gate
i'm not quite sure if it's possible but we'll see
1 5 9 13 17 21 25 29 33 37 41 45 49 53 57 61 65 69 73 77 81 85 89 93 97
3 7 11 15 19 23 27 31 35 39 43 47 51 55 59 63 67 71 75 79 83 87 91 95
notice that every 3rd integer is divisibly by 3 (rendering them even in the context of 3)
9,21,33,45,57,69,81,93
33, 37, 311, 315,...
notice that the second set multiplied by 3 equals the even set
9,21,33,45,57,69,81,93,105,129,141,...
3,7,11,15,19,23,27,31,35,39,43,47
anyone want to work on this with me?
1 3 5 7 9 11 13 15 17 19 21 23 25 27 29 31 33 35 37 39 41 43 45 47 49 51 53 55 57 59 61 63 65 67 69 71 73 75 77 79 81 83 85 87 89 91 93 95 97 99
1 5 9 13 17 21 25 29 33 37 41 45 49 53 57 61 65 69 73 77 81 85 89 93 97 101 105 109 113 117 121 125 129 133 137 141 145 149 153 157 161 165 169 173 177 181 185 189 193 197
3 7 11 15 19 23 27 31 35 39 43 47 51 55 59 63 67 71 75 79 83 87 91 95 99 103 107 111 115 119 123 127 131 135 139 143 147 151 155 159 163 167 171 175 179 183 187 191 195 199
weary gate
1 5 9 13 17 21 25 29 33 37 41 45 49 53 57 61 65 69 73 77 81 85 89 93 97
3 7 11 15 19 23 27 31 35 39 43 47 51 55 59 63 67 71 75 79 83 87 91 95
7,11,19,23,31,35,43,47,55,59,67,71,79,83,91,95
hmm interesting
55 is divisible by 5 in two ways
6,3,0
5/0 = 55?
sleek cove
pls
weary gate
7,11,19,23,31,35,43,47,55,59,67,71,79,83,91,95
7,11,19,23,31,43,47,59,57,71,79,83,91,95,
35, 55, 55
haughty lichen
lmao
abstract flax
Every time I see you, Lithium, you're just posting looooooooong strings of numbers
And I never know what you are doing
haughty lichen
he is making huge progress in inventing new math wdym - soon he will be able to find all prime numbers
weary gate
numbers that are 3 prime are divisible by 3, 1, and it self
numbers that are 1 prime are divisible by 1 and itself
wait im worng
there is one 3 prime
and it's 9
one 5 prime, and it's 25
one 7 prime and it's 49
shy latch
haughty lichen
🍿
weary gate
making progress
3 5 7 11 13 17 19 23 29 31 37 41 43 47 53 59 61 67 71 73 79 83 89 97 101 103 107 109 113 127 131 137 139 149 151 157 163 167 173 179 181 191 193 197 199 211 223 227 229 233 239 241 251 257 263 269 271 277 281 283 293 307 311 313 317 331 337 347 349 353 359 367 373 379 383 389 397 401
weary gate
MODULO-SET: 11 121 143 187 209 253 319 341
DIVISION-SET: 1 11 13 17 19 23 29 31
10, 2, 4, 2, 4, 6, 2
torn escarp
here's a bad way to find primes for you, if n!+1 = 0 mod (n+1) then n is prime
weary gate
PRIMES: 3 5 7 11 13 17 19 23 29 31 37 41 43 47 53 59 61 67 71 73 79 83 89 97 101 103 107 109 113 127 131 137 139 149 151 157 163 167 173 179 181 191 193 197 199 211 223 227 229 233 239 241 251 257 263 269 271 277 281 283 293 307 311 313 317 331 337 347 349 353 359 367 373 379 383 389 397 401 409 419 421 431 433 439 443 449 457 461 463 467 479 487 491 499 503 509 521 523 541 547 557 563 569 571 577 587 593 599 601 607 613 617 619 631 641 643 647 653 659 661 673 677 683 691 701 709 719 727 733 739 743 751 757 761 769 773 787 797 809 811 821 823 827 829 839 853 857 859 863 877 881 883 887 907 911 919 929 937 941 947 953 967 971 977 983 991 997 1009 1013 1019 1021 1031 1033 1039 1049 1051 1061 1063 1069 1087 1091 1093 1097 1103 1109 1117 1123 1129 1151 1153 1163 1171 1181 1187 1193 1201 1213 1217 1223 1229 1231 1237 1249 1259 1277 1279 1283 1289 1291 1297 1301 1303 1307 1319 1321 1327
1 5 7 11 13 17 19 23 25 29 31 35 37 41 43 47 49 53 55 59 61 65 67 71 73 77 79 83 85 89 91 95 97 101 103 107 109 113 115 119 121 125 127 131 133 137 139 143 145 149 151 155 157 161 163 167 169 173 175 179 181 185 187 191 193 197 199 203 205 209 211 215 217 221 223 227 229 233 235 239 241 245 247 251 253 257 259 263 265
4,2,4,2,4,2,4,2,4,2,4,2,4,24,2,4,2,4,2,4,2,4,2,4,2,4,2,4,2,4,2,4,2,4,2,4,2,4,2,4,2,4,2,4,2,4,2,4,2,4,2,4,2,4,2,4,2,4,2,4,2,4,2,4,2,4,2,4,2,4,2,4,2,4,2,4,2,4,2,4,2,4,2,4,2,4,2
frosty bough
wtf is going on
im so confused why u are just giving us primes
i mean thank you
but...
i mean
there are tables for this stuff
sleek cove
POSITIVE INTEGERS: 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15
sacred junco
@frosty bough 😂😂🤣
acoustic tiger
What is even happening
sacred junco
lithium is a crank
sacred junco
i invented this field a few years ago
.pin
rotund gustBOT
i invented this field a few years ago
vernal widget
sleek cove
i like ant
inner anchor
doesnt diagonalization work
modern kestrel
is that the cbs?
sleek cove
IBS?
inner anchor
wat is cbs
modern kestrel
cantor bernstein
sterile pumiceBOT
Pappa
inner anchor
if you have seen that
sacred junco
you can avoid diagonalization
first prove |R|=beth_1 and use cantor's theorem
note R is constructed by completing Q
so every $r\in\bR$ is given as $r=\sup C$ where $C\subset P(\bQ)$ the powerset of $\bQ$
sterile pumiceBOT
CityHunter
sacred junco
with usual ordering of Q
this implies $\abs{\bR}\le\abs{P(\bQ)}=2^{\aleph_0}$
and the cantor set ${\sum_{n=0}^\infty a_n 3^{-n}:a\in 2^\omega}\subset\bR$ by definition has cardinality $2^{\aleph_0}$ , hence $\abs{\bR}=2^{\aleph_0}$
torn escarp
why would you want to avoid diagonalization, it's so easy
inner anchor
probably just for the sake of it
after youve shown that |R| > |N| you can finish by riemann rearrangement which is pretty slick
sacred junco
Does this seem off?
because i thought the definition of a|b is ak=b where k is an arbitrary integer
but this looks like theyre trying to do a|b into a=bk where k is an arbitrary integer
torn escarp
this doesn't make sense to me, a|d is a statement that is either true or false, so I don't know what c|(a|d) could mean since it means c|true or c|false which aren't numbers.
sleek cove
how is you research going @weary gate
weary gate
working on a script
sacred junco
why would you want to avoid diagonalization, it's so easy
involves AC
sacred junco
probably just for the sake of it
to avoid use of axiom of choice
sleek cove
i miss lithium 
sleek cove
hmmm this is interesting 
sleek cove
it is the most interesting problem ive seen in my number theory career
acoustic tiger
i miss lithium <:pensivebread:556701306169982977>
Wait where did lithium go?
I was finally starting to notice a pattern in all of the lists he sent
sleek cove
left sigil
Real quick, and someone correct me if I'm just an idiot, but I was messing around with a bit of Sage code and apparently the jacobi_symbol(a,b) command is only defined if b is odd, but I thought the Jacobi symbol was defined for all positive integers? Or am I confusing it with the Kronecker symbol? (But I thought the Kronecker symbol just generalized the Jacobi symbol to negative integers?)
Oh wait nevermind I see what's happening, the Jacobi symbol is a product of Legendre symbols and the Legendre symbol is only defined for odd primes. I do need the Kronecker symbol for what I was doing.
sterile pumiceBOT
dusty paper
analog apex
Can anyone give a problem that can be solved using green-tao theorem?
torn escarp
no because you can't invert 3 mod 999 or 5 mod 1000
aren't you trying to find x, not a?
you can still simplify it though as it is
3x=300 mod 999 we can remove the 3 by rewriting it as 3(x-100)=0 mod 999 and since 3*something=0 mod 999 we know that this must mean that (x-100)=0 mod 333
you can do a similar trick to reduce the other congruence as well, try to simplify 4x=2a mod 1000 in the same way, show me what you get for that one @severe blade
torn escarp
I meant to put 5x=2a mod 1000, since that was your problem, but even then what you did was not right
I'll walk through the steps on this different one on accident to show the steps though,
4x=2a mod 1000
4x=2*30 mod 1000
4x-60 = 0 mod 1000
4*(x-15)=0 mod 1000
since we're making something 0 mod 1000, we know that we just need
x-15 = 0 mod 250
since when we solve that, x-5 times 4 will be 0 mod 1000
now try to do it for 5x=2a mod 1000, as a hint, the end mod will not be 250
type up/send a pic of your work in case you get the wrong answer I can see where your mistakes need to be fixed
yeah perfect
yeah exactly
if a wasn't divisible by 3 and 5, it would be unsolvable
torn escarp
no not how it works at all
it's because 3 and 5 were multiplying x
it's only when you can do that cancelling trick (if you have to do it at all) that you can solve it
3 and 5 were bad in particular because 3 is a divisor of 999 and 5 is a divisor of 1000
sterile pumiceBOT
dusty paper
sterile pumiceBOT
dusty paper
torn escarp
it just has to be a multiple of 15
because 3 is not invertible mod 999
and 5 is not invertible mod 1000
it's all because a is fixed and we're trying to solve for x, but it's multiplied by something that's making it "closer to 0"
since 3*333=0 mod 999
we can't invert it, so it has to be that 10a must be divisible by 3 as well
otherwise we can't solve that congruence
because we can't make x remove it, that'd be putting a 3 in the denominator which is not going to give you an integer solution
you should think about smaller congruences you can write out all possibilities easier like mod 12 or something
where they involve 2, 3 or 4 for instance multiplying x
for what values of a is 4x=a mod 12 solvable?
thorn bay
Hey guys is my proof valid please help me
abstract flax
Hey guys is my proof valid please help me
Being helped in #discrete-math
torn escarp
that's right but simplify a bit more, what should a be a multiple of
yup yup
you're welcome
dunno if it has a name or anything fancy, I see this as basic mod sorta manipulations
it's like you look at 3x=1 mod 6 and see it has no solutions because 3 is not invertible and 1 is not divisible by 3
sacred junco
Is there a way to define the ring of integers of an algebraic number field without mentioning Z?
mild siren
Is there a way to define the ring of integers of an algebraic number field with...
It is the intersection of all the valuation rings of the number field. But also, mentioning Z isn't that bad of a thing as Z is just the minimal (unital) ring inside of any characteristic 0 field, so it's a pretty canonical object inside of any number field.
brazen python
leaden swan
Yes
sacred junco
So I worked out (2/p) and then considered (2^m/p) but didn't really get anywhere
am tryna do the last part
inner anchor
ill just let $m = 2^n$, and then you know that $2^{2^{n+1}} \equiv 1 \pmod{p}$
sterile pumiceBOT
Pappa
sacred junco
ye so ik that 2^{p-1} = 1 and that 2^m = -1 (mod p)
sacred junco
im probs missing something but why does that imply it cant be the other way around
inner anchor
we know that the order of 2 mod p has to divide 2m
so its a power of two
but because 2^m = -1 mod p, we know that the order cant be m
so it has to be 2m
writing m as 2^n makes it a lot clearer
sacred junco
ok yeh makes sense thanks a lot
sterile pumiceBOT
dusty paper
left sigil
What you're looking for is what's called a primitive root mod 1000
We know that there are $$\phi(\phi(1000))$$ primitive roots of 1000, where $\phi$ is the Euler totient function.
sterile pumiceBOT
Bannanachair Monarch
left sigil
Using Sagemath, that means that there are 160 primitive roots mod 1000
Yeah
So that means that you'll probably only need to check about 7 in order to find one that works.
There's not really an easy formula to just produce a primitive root.
At least, not that I know.
inner anchor
Primitive roots wont exist modulo 1000
left sigil
Primitive roots wont exist modulo 1000
Why not?
sterile pumiceBOT
dusty paper
inner anchor
Primitve roots exist only mod 1, 2, 4, p^k and 2p^k where p is a prime
left sigil
Yeah, if you find a primitive root, then just changing the value of $k$ would work.
sterile pumiceBOT
Bannanachair Monarch
inner anchor
This was proven by gauss or something
left sigil
Huh, I had forgotten that.
sterile pumiceBOT
dusty paper
left sigil
So basically what the theorem is saying is that $(\mathbb{Z}/1000\mathbb{Z})^{*}$ isn't cyclic?
sterile pumiceBOT
Bannanachair Monarch
inner anchor
yes
i think for 1000 you can assume that such an a exists, then just look at it mod 125 and mod 8
then you know that $a^{\mathrm{lcm}(\varphi(8), \varphi(125)} \equiv 1 \pmod{1000}$
sterile pumiceBOT
Pappa
inner anchor
but $\mathrm{lcm}(\varphi(8), \varphi(125)) < \varphi(8)\varphi(125) = \varphi(1000)$
sterile pumiceBOT
Pappa
inner anchor
due to the totient function always being even
so the order of $a$ is always less than $\varphi(1000)$, and so a primitive root cant exist
sterile pumiceBOT
Pappa
steady nest
Hi, i need help understanding this
In $\mathbb{Z}/n\mathbb{Z}, a \in \mathbb{Z}, [-a] = -[a]?$
sterile pumiceBOT
suck2015
steady nest
oh thanks ,i don't know how i missed that
wise oyster
note also that $[-a] = [n-a]$, makes it easier to see the inverse relation
sterile pumiceBOT
Little Narwhal
rigid tusk
can someone give me a hint on this?
inner anchor
notice that $2^{3016+1} \equiv 2 \pmod{3127}$
sterile pumiceBOT
Pappa
sacred junco
can somebody give me a hint on this? i'm instructed to prove by induction
but i have no idea what to do for my base case
leaden swan
Your base case is (x-y)=(x-y)
sacred junco
how come it isn't $x^n - y^n = (x-y)(x^{n-1} + y^{n-1})$?
sterile pumiceBOT
war crime
sacred junco
where $n = 1$?
sterile pumiceBOT
war crime
haughty lichen
because it is only true when n-1>=1, so for n>=2 that we get the factors x^(n-1)+x^(n-2)y+...
sacred junco
oh i see
sacred junco
Can somebody try to guide me in the right direction. Im trying to do the inductive step in #10
rigid tusk
notice that $2^{3016+1} \equiv 2 \pmod{3127}$
so I know that a^(phi(N)) = 1 for N a composite
so multiplying a both sides
a^(phi(n) +1) = a
how do i continue?
broken igloo
witness for which test?
rigid tusk
test as in the base?
inner anchor
Now you note that 431 divides 3016+1
vital hill
wouldn't the factorisation be sqrt(-2)(1+sqrt(-2))
because sqrt(-2)(1-sqrt(-2)) = -2+sqrt(-2)
leaden swan
Check again
vital hill
how come both of these are false?
sacred junco
Why would those be true? 
vital hill
Why would those be true? <:cocatThink:827248531730726932>
what axiom do they fail
sacred junco
what axiom do they fail
have you tried doing multiplication
sleek cove
MODULO-SET: 11 121 143 187 209 253 319 341
DIVISION-SET: 1 11 13 17 19 23 29 31
PRIMES
sacred junco
you sound angry
torn escarp
he's just a lil cranky 😏
sleek cove
🥺
sacred junco
what does this mean
sage fern
so you know what balance scales look like right
sage fern
the answer is not 32
ok so you can weigh everything up to 7 pounds with 4 weights, weighing idk, 1, 2, 3 and 5 pounds each
1 = 1, 2 = 2, 3 = 3
4 = 1 + 3, 5 = 5
6 = 1 + 5, 7 = 2 + 5
sacred junco
is this a fibonacci problem
sage fern
so no matter what's on the other side, if it weighs less than or equal to 7 pounds (and the weight is a whole number), then you can weigh it with those 4
it's not a fibonacci problem
that i know of
sacred junco
because you skipped 4
sage fern
so
sage fern
no
stop guessing
just listen for a sec
you can make any number from 1 to 7 by combining some of 1, 2, 3 and 5, right?
sacred junco
yes
sage fern
that's 4 weights
but actually you can do it with only 3 different weights!
try and work out what 3 different weights you can make every number up to 7 with
that's easier than jumping all the way to 63 right away
sacred junco
how many weights max can i have on the balance at once?
sage fern
but then you can't make 1
sacred junco
2, 2, 2, 1
sacred junco
3, 3, 1
sage fern
but then you can't make 2
sacred junco
3, 2, 2
sage fern
but then you can't make 1
the only way to make 1 is with 1, so 1 will be in there somewhere
sacred junco
3, 2, 1, 1?
sacred junco
i can make 6 pounds with 3, 2, 1
sacred junco
4, 2, 1?