elementary-number-theory

[sacred junco]

so what is up with this author

x doesn't have any previous context to it by the way

Ok I think it was a typo, he just used the forward implication anyway but still sucks

[fervent crest]

Well the possible values of $x^2$ is $0,1$; the possible values for $(-1)^{n-1}$ is $-1,1$. So the possible values of $x^2+(-1)^{n-1}$ is $0-1=3$,$0+1=1$,$1-1=0$,$1+1=2$. So $x^2+(-1)^{n-1}\equiv1$ only when $x^2=0$ and $(-1)^{n-1}=1$

[sterile pumice]

Whoever:

[fervent crest]

Ah

Backward implication

[cedar badger]

Hrm

Is it true that if we have $$a^b \equiv a^{5m} \pmod{n}$$ then we have that $b = 5m$?

[sterile pumice]

Liria ^(;,;)^:

[leaden swan]

If a is coprime to n yes,otherwise no

[cedar badger]

hrm

[leaden swan]

Take a=6 and n=8

[cedar badger]

hrm

[leaden swan]

If a is coprime to n you can say a^{b-5m}=1 mod n

[cedar badger]

Naw we have that a is coprime to b but nothing about n

[leaden swan]

Ok,I don't think you can say that even if a is co prime to n

[cedar badger]

Yea

yea this is the thingy

[leaden swan]

Yea, That kinda follows directly from that euler's theorem

a^(phi(n))=1 mod n

[cedar badger]

Grouto?

Yea like the question is this, and I get that $a^b = a^{5m}$ for some integer m but I guess that Im' going about it wrong

[sterile pumice]

Liria ^(;,;)^:

[leaden swan]

Use euclid's lemma

If 5 doesn't divide b,let r be the remainder left by divison with 5

Then a^r will be 1,r will be 1,2,3 or 4

Therefore contradiction

[fervent crest]

I personally feel like it's always better to do a direct proof instead of contradiction

In this case you use euclidean division to write b=5q+r with r=0,1,2,3,4 and deduce that a^r=1(mod n) so by assumption the only possibility is r=0 or b=5q or 5|b

[cedar badger]

Hrm for this question, how do I even start? I tried throwing this into the mobius inversion formula with g(n) = sum(f(d)) but I'm not getting anywhere. This kinda look slike a flipped version of the regular formulas that they give you for mobius inversion? Because usually they have g(n/d) not f(n/d)?

[pearl jolt]

solve $\sum_{d|n} g(d)f\left(\frac{n}{d}\right) = 0$ for $g(n)$ in terms of $g(m) | m < n$ and $f(k)$

[sterile pumice]

AiYa:

[pearl jolt]

also g(1) = 1/f(1)
general case of n > 1 follow steps above

[cedar badger]

Wait what do you mean by solve it for g(n) in terms of g(m) | m < n? What is m? And how do you know that g(1) = 1/f(1)?

[sacred junco]

How do i start the proof for this one? Give the definition of ad=bd(mod n)?

[pearl jolt]

n | (ad - bd) = d(a - b) and since (d, n) = 1 n cannot divide d so n | (a - b) so a = b mod n

[cedar badger]

@pearl jolt what did you mean by solving it for g(n) in terms of g(m) | m < n? What is m, and how did you know that g(1) = 1/f(1)?

[pearl jolt]

@cedar badger if you plug in n = 1, you get g(1)f(1) = I(1) = 1 —> g(1) = 1/f(1)
by solving for g(n) in terms of g(m) with m < n, I mean finding a way to write g(n) in terms of f and previous values of g (for example, solving g(15) in terms of g(1), g(3), and g(5))

take n = 15, you have g(1)f(15) + g(3)f(5) + g(5)f(3) + g(15)f(1) = 0 so g(15) = -(1/f(1))(g(1)f(15) + g(3)f(5) + g(5)f(3))
try to generalize this method of solving to any n > 1, keeping in mind that I(n) = 0

[cedar badger]

Oh ok

I see

[forest mica]

Hi

Can anyone recommend me a book that explains clearly how to solve congruences modulo a prime power? That is, f(x) = 0 (mod p^j)

[fervent crest]

From Hardy, Wright’s “An Introduction to the Theory of Numbers”

Page 123

6th version

This depends on you being able to solve the congruence modulo p, which is hard in general

[pearl jolt]

for smaller p and j you may just want to solve f(x) = 0 mod p then write the solution as ap + b, plug that x back into f(x) = 0 mod p^2 and continue

[sacred junco]

@azure cedar PELASE

[molten verge]

hey i have a problem where i need to prove that in a domain, p having the primeness property implies irreducibility, could someone point me in the right direction?

[vestal blaze]

Apply the definition of primeness of an element p to a factorization p=ab

[molten verge]

Apply the definition of primeness of an element p to a factorization p=ab
@vestal blaze sorry do you think you could elaborate?

[pearl jolt]

if p | ab then p | a or p | b

[molten verge]

right and you want to show that if some x|p then p|x or x is a unit right?

[molten verge]

ok so i think i've made a little bit of progress

you assume x|p so p=xy for some y, then p|x or p|y by primeness

if p|x then you're done since that means x and p are associates

what do you do for the p|y case?

[vestal blaze]

write y=zp and use the fact that you are working over a domain (and not an arbitrary ring)

[molten verge]

write y=zp and use the fact that you are working over a domain (and not an arbitrary ring)
@vestal blaze ok so i'm dumb how do you use the fact that it's a domain?

[vestal blaze]

you can cancel y in y=zxy to get 1=zx, i.e. x is a unit

[storm sinew]

Im stuck on a problem that asks me to find the last digit of the number 2007^2006^2005, and so far ive gotten 9 as an answer with 2 different methods but it says that the answer should be 1? Could someone please confirm that the last digit should indeed be 1?

[stoic bear]

I got 1

[pearl jolt]

take it mod 2 and mod 5

[stoic bear]

assuming it is ((2007)^2006)^2005

[pearl jolt]

order of 2 mod 5 is 4

[storm sinew]

its written like this

i just used eulers totient function..

mustve done something terribly wrong

[pearl jolt]

ok so take the thing mod5

2^(2006^2005)

now the powers of 2^n mod 5 go like so: 1,2,4,3 for n = 0,1,2,3
so 2^n mod 5 depends on what n is mod 4
and n = 2006^2005 is 0 mod 4 so 2^(2006^2005) = 1 mod 5
2007^2006^2005 is also 1 mod 2
so it's 1 mod 10

with euler's totient function, you want 2006^2005 mod phi(10) = 8

[storm sinew]

oh wow i see

yeah i got the right answer now, ty

[cedar badger]

@pearl jolt well so far I get that $g(n) = -\frac{1}{f(1)}\sum_{d | n, d < n} g(d)f(n/d)$

[sterile pumice]

Liria ^(;,;)^:

[cedar badger]

At least that's what it looks like I'm getting

But like for the inductive step

How do you do induction with divisors?

Like I dont' see how to go and relate g(n) and g(n + 1)

Like we wouldn't necessarily have g(n) show up in g(n + 1)

[pearl jolt]

you're gonna have to find a way to formalize what I'm saying here but
you can get f(p) pretty easily right? and f(p^k) for any prime power?

if you know f(p) and f(q), can you get f(pq) for primes p and q? how about f(p^aq^b)?

[blissful rock]

2+5 = 7

[fervent crest]

succ(succ(0))+succ(succ(succ(succ(succ(0)))))=succ(succ(succ(succ(succ(succ(succ(0)))))))

[pseudo bramble]

hi, small question on the interpretation of this problem

i have the set $\displaystyle{\bigcup_{n\geq 1}\bigl[-2+\frac{1}{n^2},3-\frac{1}{n^2}\bigr]}$

[sterile pumice]

Snodlop:

[pseudo bramble]

which i'm supposed to rewrite in a simpler way "without using union"

the hint said to express it as an interval

i can express it as the interval (-2,-1] U [2,3)

but that still uses union

is that fine since it's a different use of union?

[pseudo bramble]

<@&286206848099549185> pls

sorry to ping y'all

[pearl jolt]

not helper but probably, they meant union without iteration

[mild siren]

@pseudo bramble the question is really asking: what is this set? I claim if you figure what is and what is not in this set, the right answer has a simple description in which no union is needed. In particular, your answer (-2,-1] U [2,3) isn't quite right (it's actually closer to what the intersection of all those sets would be)

[pearl jolt]

the union is (-2,3) right? cause the least upper bound would be 3 (1/n^2 approaches 0) and same for the greatest lower bound

[pseudo bramble]

there's no instance where we'd get 0 or 1 from this set tho

since we're starting from n=1

[pearl jolt]

yeah there is, you're looking at a union of intervals

in fact, 0 and 1 are contained in every set you're unioning

[pseudo bramble]

...i don't follow

can you please elaborate

[pearl jolt]

[-2 + 1/n^2, 3 - 1/n^2] contains all real numbers in between those two numbers, not only the two numbers themselves

for example, if n = 1 the the interval would be [-1, 2] which would include all real numbers between -1 and 2 inclusive not just -1 and 2

[pseudo bramble]

ohhhhhhhh

oh

i'm kicking myself rn lol

ok thank you so much

[bleak matrix]

$$2p_1…p_r+2=2n$$

n is always a prime, why?

[leaden swan]

Not always

Take p1=3 ,p2=5

[bleak matrix]

Wait..Show it?

[pearl jolt]

2 x 3 x 5 + 2 = 32

[bleak matrix]

$$p_1…p_r$$ are prime ≥2

Ok

[leaden swan]

Euclid's proof can not be used for generating primes

[pearl jolt]

no, you did not just find a prime generating algorithm lol

[bleak matrix]

Wait, what? Lol

[crisp steppe]

im trying to use multinomial theorem for this

its probs overkill but it doesnt seem to work and idk why

x^3 * y^5 = (xy)^3(y)^2
i get Nc(3! * 1! ) = Nc3 but that isnt right

[pearl jolt]

@crisp steppe in order to get x^3y^5 you need 3 xy factors, 1 y^2 factor, and n - 4 1 factors, this is equivalent to arranging a string with 3 A's, 1 B, and n - 4 C's (think of each factor as a letter)
there n! total letters, but we overcounted the A's by a factor of 3!, the B's by a factor of 1!, and C's by a factor of (n - 4)!
putting it together, that's n!/(3!(n - 4)!) = n * (n - 1)!/(3!(n - 4)!) = n * C(n - 1, 3)

[steady wadi]

Let $21x{i+3}+20x{i+2}+19x_{i+1}=x_i^2$, where $i \in { 1, 2, \dots , n }$, $x_1, x_2, \dots, x_n \in \mathbb{R}+$, and $n \in \mathbb{Z}+$ and $n > 3$ (indices are taken $\mod{n}$). Find all ${x_i}$ satisfying this equation.

[sterile pumice]

popoke:

[fervent crest]

Ok the indices are weird

If you take them mod n then they might be 0

So I assume you mean $x_0,x_1,\dots,x_{n-1}\in\bR^+$ and $n\in\brc{4,5,\dots}$ and $x_i^2=19x_{i+1}+20x_{i+2}+21x_{i+3}$ for $i=0,1,\dots,n-1$ where the indices are taken modulo $n$

@steady wadi

[steady wadi]

yea

[sterile pumice]

Whoever:

[fervent crest]

Lmao I just didn't even write the x's in there

hmmm

[steady wadi]

yea I figured

I noticed that any amount of 60s always works

and $\min_ix_i\leq60\leq\max_ix_i$

[sterile pumice]

popoke:

[fervent crest]

I conjecture the only solutions are x_0=x_1=...=x_{n-1}=60

Can I prove it?

Nope

[steady wadi]

definitely not

take for example

x_1 = 9
x_2 = 1
x_3 = 1
x_4 = 2

[fervent crest]

Um

But $x_2^2=1\neq248=19\cdot1+20\cdot2+21\cdot9=19x_3+20x_4+21x_1$

[sterile pumice]

Whoever:

[steady wadi]

isn't it

$x_1^2 = 19x_2 + 20x_3 + 21x_4$

[sterile pumice]

popoke:

[fervent crest]

But i can be 1,2,3,4,...,n

So it's n equations simultaneously

[steady wadi]

the sequence isn't infinite tho

you can choose how long it is I thought

[fervent crest]

Still it has to satisfy your equations lmao

[steady wadi]

no but

isn't that the only equation

for a sequence of length 4

like

[fervent crest]

No

[steady wadi]

oh

nvm

[fervent crest]

Let's look at what you wrote

https://cdn.discordapp.com/attachments/418981682117345288/767229523342655498/767187916710871076.png

[steady wadi]

I forgot about the

how indices are mod n

[fervent crest]

Yeah

And what you wrote doesn't quite make sense either

[steady wadi]

that's how the question is phrased

[pearl jolt]

so is the sequence infinite or does it only go up to n or...

[steady wadi]

I guess I am misinterpreting it

[pearl jolt]

I am very confuse

[steady wadi]

it only goes up to n

but in the equation

if you plug in i = n

then i + 1 = n + 1

but since indices are mod n

[pearl jolt]

I see what you mean

[fervent crest]

so you go back to 1

[steady wadi]

it's just the x_1

yea

[fervent crest]

ah I guess that makes sense in some way

nvm

Well I plugged it into wolfram alpha for the cases of n=4 and 5 and the only real solutions it gave me were all 0's and all 60's

[pearl jolt]

sum(x_i^2) = 60 sum (x_i)

[fervent crest]

Yeah

[steady wadi]

I see

hard to prove tho

[fervent crest]

Ah nvm

[steady wadi]

rip

what was the idea

[fervent crest]

Well choosing the smallest element and the largest element

But I only showed min(x_i)≤60≤max(x_i) like you said

[steady wadi]

oh

[stoic bear]

I do not understand the problem

[steady wadi]

what part don't you understand

[stoic bear]

Nvm, I figured it out

I was confused on the indices mod n for a bit

[steady wadi]

ah

[sterile pumice]

Whoever:

[fervent crest]

Ok my original ideal worked

Fuck

@steady wadi so the maximum is smaller no more than 60 and the minimum is no less than 60

this means that all the numbers are between 60 and 60

or all numbers are just 60

[stoic bear]

huh

[fervent crest]

Is texit dead

damnit it is

[steady wadi]

wait

oh

wait

I think I may have showed that too

but misinterpreted

[fervent crest]

lmao

[steady wadi]

was that your original result too

[fervent crest]

yes

i'm furious right now

[steady wadi]

lmao

[fervent crest]

anyways

[steady wadi]

thanks

I'm kinda mad too

[fervent crest]

math is dumb we should all learn computer science instead

[steady wadi]

lol

Wise words

anyways

[stoic bear]

@fervent crest begone, learn chem

[steady wadi]

I got some graph problems too

might post them here too

what channel should they go in

#discrete-math

or

#combinatorial-structures

[stoic bear]

#discrete-math or #competition-math if contest

[steady wadi]

ok

got another question

which I sort of have the solution too

but not sure if it's right

so basically

I wanna find all $x$

so that

there exists positive integers a, b

so that $e^{xa}$ is divisible by $2020^b$

and I thought about this

and after the substitution $x = \ln{y}$

I came to the conclusion $y$ has to be a product of powers of 2, 5, and 101, where the exponents can be any rational number

[sterile pumice]

popoke:

[steady wadi]

so the set of all x is $X = { q_1 \ln{2} + q_2 \ln{5} + q_3 \ln{101} \mid q_1, q_2, q_3 \in \mathbb{Q} }$

can anyone check my reasoning on this?

[sage forge]

can someone help me with this
Find all positive integers z for which z^4 + 4^z is prime.

[fervent crest]

For $z$ even it's clear that it $z^4+4^z$ is not prime. For odd $z$ use sophie's identity, namely $a^4+4b^4=((a+b)^2+b^2)((a-b)^2+b^2)$

[sterile pumice]

Whoever:

[bronze breach]

Hey guys,

I'm trying to solve a problem, and I've reduced it into figuring out what are the integer values of x which will result in ax^2 + bx + c being a perfect square. Any ideas for how to tackle this?

[sleek cove]

are there restrictions on a b and c

[pearl jolt]

maybe bound ax^2 + bx + c in between two perfect square trinomials

[cedar badger]

@pearl jolt I'm not really sure that I see a pattern for g(p^k)? I see that $g(p) = -\frac{1}{f(1)}(g(1)f(p)$, but then I tried to go and take powers of 2 and 3 but I dont' see a patter nother than $g(n) = -1/f(1) \sum_{d | n, d < n} g(d)f(n/d)$

[sterile pumice]

Liria ^(;,;)^:

@AiYa I'm not really sure that I see a pattern for g(p^k)? I see that $g(p) = -\frac{1}{f(1)}(g(1)f(p)$, but then I tried to go and take powers of 2 and 3 but I dont' see a patter nother than $g(n) = -1/f(1) \sum_{d | n, d < n} g(d)f(n/d)$
```Compile error! Output:

! Missing $ inserted.
<inserted text>
$
l.54 ... really sure that I see a pattern for g(p^
k)? I see that $g(p) = -\f...
I've inserted a begin-math/end-math symbol since I think
you left one out. Proceed, with fingers crossed.

LaTeX Font Info: Calculating math sizes for size <14> on input line 54.
LaTeX Font Info: Try loading font information for U+msa on input line 54.
(/usr/local/texlive/2018/texmf-dist/tex/latex/amsfonts/umsa.fd

[cedar badger]

hrm dunno where that went wrong

And I can't really seem to go and find a general pattern for g(pq)

Ocr at least I'm not getting anywhere with it

Like I see that I have $g(6) = -1/f(1) (g(1)f(6) + g(2)g(3) + f(3)g(2)$ but that does not look like it has any direct relation to 3 and 2?

[sterile pumice]

Liria ^(;,;)^:

[cedar badger]

Other than the fact that the prime factors do indeed appear in it?

Like I think that what you're suggesting is to go and dos moething with prime and composite numbers yea?

[cedar badger]

but I dont' see anything to do with multiplicity

[pearl jolt]

you got g(6) in terms of g(3) and g(2) and g(1), and you know how to find g(2) and g(3)
from f(1)g(3) + f(3)g(1) = 0 —> g(3) = -f(3)g(1)/f(1)
and in general, f(1)g(p) + f(p)g(1) = 0 —> g(p) = -f(p)g(1)/f(1) for any prime p
you know that g(n) = -1/f(1) [sum((over the proper divisors of n) g(d)f(n/d)) = -1/f(1) (g(1)f(pq) + g(p)f(q) + g(q)f(p)) where p and q are prime
and we've already established how to find g(p) and g(q)
so is that clear on how to find g(pq)? if so, try finding g(a prime power of p)

[cedar badger]

Uh

Not really

let's say g(4)

$g(4) = -1/f(1) \cdot (g(1)f(4) + g(2)f(2)) = -1/f(1) \cdot (g(1)f(4) -g(1)f(2)/f(1) * f(2))$

[sterile pumice]

Liria ^(;,;)^:

[red saffron]

shouldn't this say p_2 ... p_t < n? then that means that p_2 ... p_t has a unique factorisation since each of the numbers 2, ..., n-1 has one by our induction hypothesis

also p_s too right?

[leaden swan]

Well if it's less than n it's less than n+1

[red saffron]

yeah i know but

[leaden swan]

Yea,typo ig

[red saffron]

is the t subscript instead of s also a typo?

kind of confused

[leaden swan]

No

That has to be shown separately

[red saffron]

i read up to p_2 ... p_s = q_2 ... q_t and then i don't get the next sentence

[leaden swan]

By induction,there can only be one unique factorisation

(Assuming s<t)So,p_2 has to be q_2 ,p_3 has to be q_3....p_s has to be q_s,and there are no more primes

[red saffron]

ohhh i get it cuz it's a unique factorisation

[wary yew]

hey people need spme help...got to proof that 3n²-1 can't be the square of any natural number

[pearl jolt]

3n^2 - 1 = 2 mod 3 which is not a square residue because 1^2 = 1, 2^2 = 4 = 1, 0^2 = 0 mod 3, perfect squares are never 2 mod 3

[wary yew]

thanks a lot!!

[cerulean plover]

Can anyone help me woth this

I have to find any b, for which this always is true (no matter what x)

Answer is b=1 since the resulting number and 1003 are both divisible by 17, but idk how to get to it

[sacred junco]

Whys is e^(50/e) the largest product

Where does e come into this

(I'm sorry if this can't a number theory question, wasn't sure where to post it )

[fervent crest]

By numbers do you mean real numbers or rational or natural

Positive or all real/rational/integer

[sacred junco]

Positive real

[fervent crest]

Well you can use am gm inequality probably

So if $a_1,\dots,a_n$ are nonnegative, then $\prod_{i=1}^na_i^{1/n}\leq\sum_{i=1}^n\frac{a_i}{n}$, or $\prod_{i=1}^na_i\leq\br{\sum_{i=1}^n\frac{a_i}{n}}^n=\frac{\br{\sum_{i=1}^na_i}^n}{n^n}=\frac{50^n}{n^n}$

[sterile pumice]

Whoever:

[quartz gate]

i dunno if this is the right channel but is there a way to show this:

[quartz gate]

<@&286206848099549185>

[bleak matrix]

Is there a pattern to this sequence: 6,14,30,61,124,250,502,1006,2014?

[sleek cove]

thats cringe

[willow knot]

how do I show that 2^19+5^40 is not prime

[vestal blaze]

Mod 3

[bleak matrix]

thats cringe
@sleek cove what?

[stoic bear]

No obvious pattern I can see, assuming you copied it down correctly

[bleak matrix]

No obvious pattern I can see, assuming you copied it down correctly
@stoic bear I made a quick research about the sequence it's called holonomic or D-finite, what does it mean? Can you explain it in layman terms

[bleak matrix]

I'm just playing around with odd numbers and I eventually saw this numbers it seems nonsense, but I needed to know more about it, there is something interesting to it, so I asked about it here. And also the words you asked is something related to odd numbers particularly in polynomials and sequences. I don't know much about it either...

Sorry for the English..

I'm looking to some related topics about odd numbers on MathWorld and Wikipedia there I got those words. Its when you multiply every prime numbers ≥2 in the descending order times 2

You can find it, if you play around with it

[sleek cove]

61 is prime

[bleak matrix]

Yes

[stoic bear]

"Its when you multiply every prime numbers ≥2 in the descending order times 2"

what

[bleak matrix]

Sorry my bad English

[stoic bear]

This does not generate your sequence

[bleak matrix]

Yes it's not, I don't remember the procedure I did. It is like, multiplying the numbers to 2 and if you get even you divide and add and again..

Yes

Sorry my bad..

[sleek cove]

[sterile pumice]

niuton:

[fervent crest]

no

it definitely does not work like that

Let's say by a mod b you mean the remainder of a divided by b

Then

$(m\mod n)^d=m^d\mod n$

[sterile pumice]

Whoever:

[leaden swan]

Use ab mod n =(a mod n) (b mod n) mod n

Yes

(For an example take a=3 ,b=5 and n=6 ab=15, remainder of 15 with 6 is 3.

Remainder of 3 with 6 is 3 and remainder of 5 with 6 is 5. Product of remainders is 15 which leaves a remainder of 3 with 6)

That's the rule,I don't think it has a specific name

[simple carbon]

Hi all. Could use some help with this problem. For context we just covered Fermat's Little Theorem. May not be applicable here though

I found a solution to it here: https://www.math.uwaterloo.ca/~snew/Contests/ProblemSessions/Problems2016/Lesson6soln.pdf Although given the "hint" i think there may be some better way of doing it.

[vestal blaze]

I think the hint suggests to look at $n^4 + 4^n$ mod 5, because then $n^4+4^n\equiv 0 \mod 5$ for those $n$ that are odd and not divisible by 5

[sterile pumice]

leoli1:

[vestal blaze]

but I don't see how to do it mod 5 for the general n

[simple carbon]

Ahh, thats neat, thanks. I thought of mod 5 a few times but did not realize you could prove it was 0 mod 5 in those cases. Maybe will have to consider n being a multiple of 5 as a special case.

[simple carbon]

Well for n=5, 15, 25, ... the result seems to always end in 49 🤷‍♂️

[sacred junco]

thats because 49 is the number theory constant.
all numbers in number theory seem to always end in 49.

[leaden swan]

2^2=4

[sacred junco]

theres a hidden 9 at the end of it

[tiny ravine]

Hey

Whats 2 plus 2?

[leaden swan]

That's not funny

[red saffron]

can i use fta for this

like for example show that 3 divides any power of a prime in x

[manic arch]

yeah that's one way to do it

[red saffron]

thanks

@manic arch is there a better way you'd do it?

[manic arch]

I was thinking just about that, haven't done these in a while. Maybe by contradiction (think the proof that \sqrt 2 is irrational) but that appeals to the FTA too, so it's probably better to do it directly as you propose

[red saffron]

thank you very much

yeah

[simple hearth]

I would use unique factorization

which I guess is what you mean by FTA!

My favorite unique factorization problem is : Prove that for integers x and y we have : gcd(x,y) * lcm(x,y) = x*y

[sacred junco]

why

[swift shard]

why

[manic arch]

why

[fervent crest]

why

[sacred junco]

because

[olive gull]

Hi all,
I have a question about the GCD and the LCM of two numbers. It's a question between mathematics and algorithmic.
My problem is to compute the sum of LCM(i, j), with i, j <_ 1e18. So, it is a very large input, and I have only a few time (arround 5 / 10 sec) to compute them. I try a lot of algorithm like the euclidian algorithm, but it is too slow, I tried some binary GCD algorithm, but it's to slow, and I finally tried to use the Euler totient function. I have good time result for a i, j < 1e8, but if I increase my n, the time is very very slow.
So my question is :
Do you have an idea of an existing algorithm / formula to solve my problem ? I think it's in the direction of the Euler Totient function, but I'm not sure (it can be in an opposite way, ahah)
Thanks,

[torn escarp]

is this some project euler problem

[fervent crest]

https://projecteuler.net/problem=379

Similar

[torn escarp]

I saw you talking about it in adv nt, did you end up solving it or did you lose interest

[fervent crest]

I didn't try very hard and something else came up

[tender light]

what is major difference between euler theorem and fermat little theorem

ok, thanks

[olive gull]

@fervent crest @torn escarp I don t have any answer in advanced, and I didn t lose interst... I m just sleeping... I m going to continue to try today

[sacred junco]

(76^63 + 66^53 )mod 71

[bleak matrix]

Can someone give me a details about this zeros of polynomial: $(x-p_1)(x-p_2)…(x-p_n)$ I want to know more about this, $p_n$ are the n-th primes

[sterile pumice]

Not so spooky user:

[leaden swan]

Roots are p_1,p_2...p_n

[bleak matrix]

Yeah, but is there a an algorithm to generate a polynomial that has a zeros $(x-p_1)(x-p_2)…(x-p_n)$

[sterile pumice]

Not so spooky user:

[torn escarp]

suppose you have $f_n(x)=(x-p_1)\cdots(x-p_n)$ then to get $f_{n+1}(x)$ the algorithim is you simply take $f_n(x)$, now make two separate polynomials by multiplying it by $x$ and $p_{n+1}$. Then subtract the second from the first, like so, $f_{n+1}(x) = x*f_n(x) - p_{n+1}*f_n(x)$ and there you go, now you can iterate this algorithm to generate any one you like @bleak matrix

[sterile pumice]

Merosity:

[bleak matrix]

I don't understand.. please tell more

[fervent crest]

Basically just use the distributive property to find the polynomial

[sacred junco]

please help me :

solve over the positive integers x^(2y) - 5x^2 = 300.

please

[meager pond]

@sacred junco I think the equation has no solutions

x^2(x^(2y-2) - 5) = 300

look for factors of 300 that are a perfect square (x^2)

then try to find solutions for y

[sacred junco]

@meager pond thank u some much!

[meager pond]

Np

[bleak matrix]

Basically just use the distributive property to find the polynomial
@fervent crest Yup, but is there a pattern to its numerical coefficient for how its distributed, I mean like the binomial theorem

[fervent crest]

Aside from the general pattern idk if there’s any pattern specifically because they’re primes

So if $(x-p_1)(x-p_2)\cdots(x-p_n)=x^n+a_{n-1}x^{n-1}+\cdots+a_1x+a_0$ then $a_{n-1}=-\sum_{1\leq i\leq n}p_i$, $a_{n-2}=\sum_{1\leq i<j\leq n}p_ip_j$, $a_{n-3}=-\sum_{1\leq i<j<k\leq n}p_ip_jp_k$ and so on

[sterile pumice]

Whoever:

[fervent crest]

That the coefficients are elementary symmetric polynomials of the roots

@bleak matrix

idk what you're trying to do

[sacred junco]

am i just expected to multiply some rather large numbers for this

or is there a better way somehow

I would use Euclid's to find the numbers in Bezout's to find the inverses then use CRT to find x mod 900*841 is that the best way to go about it

seems weird cuz usually itd be non-calc

[cedar badger]

I'm not sure where to start with this

The only thing that I can think of with (a, n) = 1 is Euler's Theorem but I don't think that's what we're really looking for here?

[leaden swan]

k-l will be a multiple of phi(n)

$a^{k-l} \equiv a^{\phi(n)x} mod n \equiv 1^x \equiv 1$ mod n

[sterile pumice]

DrunkenDrake:

[cedar badger]

Oh

Becaues k = l mod phi(n) means that k - l | phi(n)

[sacred junco]

(\pmod{} for cool mod)

[sacred junco]

find all a, b positive integers such that :
a^2 b^2 - 4(a+b) = n^2

hint please

[cedar badger]

I'm stuck on this question

I can see that if we have $n^{p - 1} \equiv 1 \pmod{p}$ then we can go and take the square root of both sides to give us $n^{(p - 1)/2} \equiv \pm 1 \pmod{p}$

[sterile pumice]

Liria ^(;,;)^:

[cedar badger]

But I dont' see how we can go from that to $p | m - 1

[leaden swan]

$p \mid n^{p-1} -1 \implies p \mid m^2-1$

[sterile pumice]

DrunkenDrake:

[leaden swan]

And your conclusion follows

[cedar badger]

wait

Why does $p | n^{p - 1} - 1$

[sterile pumice]

Liria ^(;,;)^:

[leaden swan]

Fermat's little theorem

[cedar badger]

Isn't Fermat's little theorem the other way around?

Or have I been flipping it raound the whole time

[fervent crest]

That's rewriting $n^{p-1}\equiv1\pmod{p}$ using the definition of $a\equiv b\pmod{n}\iff n\mid(a-b)$

[sterile pumice]

Whoever:

[cedar badger]

oh wait yea I flipped it around

[cold lily]

Y'all I'm new to this Discord so I hope I'm asking this in the appropriate location. Is there somewhere I can find a proof that if P is the product of two prime numbers, P only has 4 factors.

[fervent crest]

You can read on number of divisor function

And what you said is only true if the primes are distinct

[cold lily]

For distinct primes!! Thank you!!

[fervent crest]

induct

proving it for t=1 should be fairly obvious

then i think you need to induct

on t

[hollow bay]

how would i got about showing this? no clue

x=1 is a solution and x=-1 is also for any p and t I choose, so do I have to prove that other than those there aren't any more solutions?

[simple hearth]

I assume the last "mod p" should be "mod p^t"

otherwise this would be a really strange question

[hollow bay]

i thought about that too, should I assume that?

if it's p it either makes no sense or a hard question which it shouldn't be so...

but assuming its mod p^t and not mod p how should I go about it?

[simple hearth]

prove it mod p and use Hensel lifting?

I'm not sure what tools you have that you can reference

[hollow bay]

never heard of that

so pretty much nothing

I guess only the definition of a congruence and not much else

[simple hearth]

ahh, so yes, this is not that bad to do directly from the definition of congruence

so, prove it for p. That's the base case of your induction.

then assume it is true for p^t and prove it is true for p^(t+1)

Hint: You can interpret numbers mod p^(t+1) as numbers mod p^t. (This is where you need to get your hands dirty with the definition of congruence)

[hollow bay]

ty i will try with that

[simple hearth]

This is a cool problem, I might steal it for number theory next semester.

[hollow bay]

but just to make sure, it doesn't make much sense if the question asks mod p right?

so i can assume it's a typo

[simple hearth]

I would, yes

[hollow bay]

@simple hearth hello, im sorry to tag you but i can't seem to do it and it's pissing me off. This is what i've done:
So i wanted to show that x^2 is congruent to 1 mod p for the base case and so I used the definition of congruence which tells me that p divides x^2-1 and so it divides (x+1)(x-1) which means p divides x+1 or p divides x-1 and solving those two I get x=1 and x=-1. Now for the induction step I can't seem to find out where I'm supposed to use the fact that x^2 is congruent to 1 mod p^t. Is my way of proving that x^2 is congruent to 1 mod p only has 2 solutions even correct?

[supple furnace]

You don’t need induction either. Just note that we can’t have p dividing both x-1 and x+1, which means that the whole p^k must divide one of them.

[hollow bay]

but how does that show that there are only 2 solutions?

[sleek cove]

contradiction

[hollow bay]

how do we get a contadiction? I get to p | (x-1)(x+1), but that just means it must divide either one of them and thus we got the 2 solutions

or can I just say--> "Since we have p^t | (x-1)(x+1) and so we can only have 2 solutions"?

[cyan tendon]

Hello, I heard elliptic curves are quite the hot topic in number theory and cryptography, would anyone happen to know of resources to get started on them? (currently looking through wikipedia lol)

[mild siren]

@cyan tendon I'd recommend either "Elliptic Tales" by Ash and Gross or "Rational Points on Elliptic Curves" by Silverman and Tate, depending on your level

[cyan tendon]

I know a lil bit of arithmetic but not much (sorry if it's vague /x)

Thank you for the recommandations :D

ah no, basically I know some prime manipulation, a little bit of congruences, divisibility relations & pgcd, bezouts & gauss theorem, and that's about it
So not much

ok, thank you both 😄

I'll put in on the list~

[cedar badger]

For this question here, I can go and get like... halfway, but I don't know how to go and take the last step; in the direction of "If this has a solution, then $(n_1, n_2) | (a_1 - a_2)$", I get to the point where I have $a_1 - a_2 = tn_2 - sn_1$, which I see is in a form where Bezout's Lemma can apply to give us that $a_1 - a_2$ is... related to the gcd anyways, not sure where to go from here.

[sterile pumice]

Liria ^(;,;)^:

[fervent crest]

well $(n_1,n_2)\mid n_1$ and $(n_1,n_2)\mid n_2$ so $(n_1,n_2)\mid -sn_1$ and $(n_1,n_2)\mid tn_2$ so $(n_1,n_2)\mid tn_2-sn_1=a_1-a_2$

[sterile pumice]

Whoever:

[cedar badger]

Oh true

because common divisors

and integer combination thingy

[fervent crest]

Yeah

Bezout's lemma states that $\brc{tn_1+sn_2:t,s\in\bZ}=\brc{t(n_1,n_2):t\in\bZ}$

[sterile pumice]

Whoever:

[cedar badger]

Hrm

Ok

I think that I know how to do it in the other dierction then.

[hearty wadi]

How to show that Fermat pseudoprime is relatively prime to its base?

[hearty wadi]

Ah I get it, in short - since this stuff has inverse

[final beacon]

If a set has the same cardinality as an infinite set, how do you show that that set is also infinite?

This seems extremely intuitive, but I can’t figure it out for the life of me

[calm glen]

Forgive me if this the wrong section but Im trying to find what a limit/series converges to.

Lim x->infinity of (1/x)× (series of n=1 to n= infinity of 1/n)

[sacred junco]

do you know how 1/n series behaves?

as in order

[swift shard]

The sum doesn't converge. Are you sure you didn't mean series from 1 to x?

[sacred junco]

its inf/inf kaynex

[calm glen]

The sum doesnt converge but im dividing by a variable which tends to infinity

I suspect that'd be enough to make the series converge but I could be wrong

[swift shard]

Yes, but the series just doesn't converge no matter what x is.

That's like dividing something that doesn't make sense by something that is growing towards infinity

[sacred junco]

oh yeah you should make the series from n=1 to x

good point

[calm glen]

@swift shard Whats the proof of that look like?

It sounds dumb I know

[swift shard]

Oh, so that is the question haha

[calm glen]

But Im working in a space that includes infinity as a point

So I want to make sure it doesnt affect the convergence of non-covergent series

[sacred junco]

can you use the fact that $\sum_{n=1}^{k} \frac1{n} \cong logk$ ?

[calm glen]

Maybe?

[sterile pumice]

Godel:

[sacred junco]

then you can look at the lim log x/x right

[calm glen]

Id suspect if you can shove a greater than/ equals to in there after some k value than it'd help but

[swift shard]

Basically that's like inf / x

For an x that's always real

You're getting inf

[calm glen]

For an x on the extendes real line

So inf/inf is "allowed"

Im just not sure how to handle asking "which infinity blows up faster and by how much?"

[sacred junco]

you can put some inequalities on logn I suppose

[swift shard]

Well, nothing blows up to inf as fast as the element inf

Which is what you've got, haha

[sacred junco]

hmmm, how would you then think about log(inf)/(inf)

if inf is in the set

[swift shard]

Like, choose an x that's very large. You'll have
inf/very large number

Still inf, no matter which x you choose

[calm glen]

Ye

[sacred junco]

unless you choose x=inf

[swift shard]

[calm glen]

Or what if you chose lim x -> inf?

[swift shard]

You've gotta dissect what a limit is asking here. You can never really plug in inf, but the limit is asking for very large real values of x

[sacred junco]

kaynex he is talking about extended real line so I think there should be argument for that to work

so you could plug in inf maybe?

[swift shard]

I think there's fundamental flaws with letting paths approach the literal element inf but that's above this question I fear

[calm glen]

What are some resources I can check out?

[sacred junco]

I guess it depends on the definitions, just like if you think only about homographies as functions, making infty a number may make sense if you define it well

[calm glen]

Frankly its only not defined by constuction of integers because we'd have to consider the existence of an infinite sum but frankly I dont see why not

[swift shard]

Like, normally when given
"lim as x approaches infinity"
That's really asking about an ε-δ argument. As x > N, |L - f(x)| < ε

But f(x) is infinity for all x

That is, if you interpret that summation as infinity, which is already ehh

This question would be much more interesting if it were the sum from 1 to x

[calm glen]

Im considering that sum as well

Im considering the idea of adjusting divergent series by "dividing by infinity" to see what it takes to make them converge and what they converge to

1 to X there exists a descusion on convergence for sure but I feel 1/X might be an easier to handle problem

And I wanna start easy and think about whats going on before I start working out the details

But its something I havent worked with before and was just wondering if anyone could point me in the right direction

[swift shard]

But you're not dividing by infinity. You're dividing by an increasingly large, real x

f(x) = inf/x = inf, in a sense

[calm glen]

Theres subtleties of this idk how to handle. Like what if we considered instead a double limit?

A limit of the sum and a limit of x?

Both going to infinity. Which reaches faster?

[swift shard]

Well that depends on the relation of the sum to x

If you're interested in the sum between 1 to x, then you have ln(x)/x which approaches 0

[calm glen]

Actually ye that seems to be a good way of handling things to start. Taking bounds/approximations to sums and considering limits

[bronze python]

I didn't understand how contradiction of the fact we assumed, proved that it's true

[bronze python]

<@&286206848099549185>

[sacred junco]

That's kinda how proof by contradiction works.You want to prove p is true. If you show that (not p) is false, then p has to be true

but why does contradiction of the assumption that 'p and q have no common factors' work here?

why do we assume that p and q have no common factors in the first place?

[bronze python]

wait, they already claimed that p and q have opposite parity and no common factors right?

[leaden swan]

Because we want a unit like triplet

From which we can construct all other things

[sacred junco]

there are 2 cases , one if p and q have opposite parity and one if p and q have same parity (both p and q have to be odd in this case since if they were both even they would have the common factor 2)

[leaden swan]

Because if p and q have common factors,that triplet won't be unique
Ignore this

[bronze python]

so d is a common factor for p and q, the triplet won't be unique?

@sacred junco

[sacred junco]

I think you pinged the wrong person it was drake who said that

[bronze python]

ok sorry

@leaden swan bro little help?

[leaden swan]

Ignore that statement

[bronze python]

It's just that I'm having trouble understanding this

[sacred junco]

if d is a common factor for p and q, then p and q won't be of opposite parity @bronze python

but then why does hatcher assume that fact for the second case also where p and q have the same parity

I think to show that will imply they have a common divisor which would be a contradiction.

so those two cases imply that p,q dont have the same parity and dont have any common factor ( since those statements 'negate/contradict' each other)

[bronze python]

if d is a common factor for p and q, then p and q won't be of opposite parity @bronze python
@sacred junco won't that mean that the triples aren't primitive?

[sacred junco]

wait what does primitive mean

[bronze python]

like, having no common divisors

[sacred junco]

oh fuck I didn't realize that hatcher was talking about primitive triples

then the proof makes sense

because they are co-primes they don't have a common divisor other than 1

so they can't have a factor in common

and that's why the contradiction works

[bronze python]

okay

[forest mica]

Is anybody here interested in being part of a number theory study group?

[swift shard]

What level? Elementary?

Have a book in mind?

[forest mica]

I would like to start with the basics so that anyone can join. Yes, two in fact. "An Introduction to the Theory of Numbers", Wiley, and maybe "An Introduction to Analytic Number Theory" by Apostol (this one aftrer having read the first one or, at least, a good part of it)

[lusty hornet]

I would like to join the number theory group .

But I haven't studied it much though, only a bit of the beginning stuff

[shrewd marsh]

I'll join

[orchid wagon]

I'd join as well. I also have a book suggestion if you're interested — An Illustrated Theory of Numbers by Martin Weissman, published by AMS

[oak solstice]

Is anybody here interested in being part of a number theory study group?
@forest mica If it's not a problem that I have almost 0 knowledge of number theory, then I'd like to join aswell

[leaden swan]

Yea,It's not

[forest mica]

Please, those who want to join it, dm me

We are waiting for some more people to join before starting

[native zenith]

does downloading discord app make the images uploaded sharper?

[leaden swan]

Solve for n,k $\in \bZ$:
2(n-2)! = $2^k$ (n-2k)! k!

[sterile pumice]

DrunkenDrake:

[leaden swan]

nvm, got it

[hollow bay]

Hi I have a question.
A number n is a pseudo-prime base 2 if 2^(n-1) is congruent to 1 mod n.
I need to show that if n is a pseudo-prime then 2^n - 1 is also a pseudo prime.
Which one of these is equivalent to the thing a want to prove:
(1) 2^(2^n-2) is congruent to 1 mod n
(2)2^(2^n-2) is congruent to 1 mod 2^n-1
Basically, what mod do I need to prove it for?

[leaden swan]

2

[hollow bay]

alright ty!

[storm sinew]

are there any effective ways of solving problems like this? " if m=32!, then what is true about m?"

[stuck lintel]

For lower bound, you can round each number down to the nearest power of 2

For upper bound just round up

[storm sinew]

ohh i see

thank you

[fervent crest]

You’re welcome

[sleek cove]

thanks

[sacred junco]

np

[stoic bear]

Anytime

[manic arch]

nesting the "mod c"s has no well defined meaning, are you trying to prove that multiplication of equivalence classes is well defined or something akin to that?

[sacred junco]

7x^8 - 8y^7 = 1984, x, y are positive integers.
how we can prove there are no solutions?

[supple furnace]

||Notice that x is even. Let x=2k to get 7(256k^8)-8y^7=1984. Dividing by 8 gives 224k^8-y^7=248. This implies that y is even. Set y=2l to get 224k^8-128l^7=248. Divide by 8 to get 28k^8-16l^7=31, a contradiction.||

[sacred junco]

thank youu very much !

[manic arch]

I meant equivalence classes, sorry about that

The notation (mod c) is different from the modulo operation often implemented in e.g. programming languages. Addition or multiplication modulo c is an operation defined between equivalence classes of integers and not the integers themselves

so there's no real need to give meaning to something like $(a \pmod c + b) \pmod c$ since you'd just take $a$ as a representative of the class $a+c\bZ\coloneqq {a+cz~|~z\in\bZ}$, and then consider $a+b\pmod c$, which is the equivalence class $(a+b)+c\bZ$.

[sterile pumice]

derivada.schwarziana:

[sleek cove]

yes

[covert wing]

ZHENG HE

omg

youre so amazing im ur greatest fan

[last egret]

hi

[manic arch]

Are you saying that in programming the notation "a%c" is an operation that returns the remainder of a/c
but in math "a mod c" is more like a notation for the equivalence class "a+cZ"?
exactly what I meant

[bleak matrix]

Is there any effective way of learning how to construct a good proof? I'm getting frustrated whenever I build my proof. I think my method is not that effective on proving problems, it takes me a week to solve an elementary number theory problem, I need to re-read my previous work on some of the problems I solved. And it takes me a lot of time to realize what I needed to do. Arghh!😩

[static sapphire]

Do you have a picture of what your proofs look like? @bleak matrix

[zealous violet]

any one know the awnser?

[sleek cove]

i think the expression on the left equals integer

[lusty hornet]

what is the question? what do you need to find

[leaden swan]

I guess find x,y such that the express is an integer for all a>1

[lusty hornet]

Isn't only when x=y ?

and when x and y are not equal to 0

[leaden swan]

iff y divides x

[leaden swan]

Use $gcd(x^a-1,x^b-1)=x^{gcd(a,b)}-1$

[sterile pumice]

DrunkenDrake:

[hexed echo]

Can anyone tell me about Kobayashi's theorem. (In detail)

I really need it for my International Mathematical Olympiads preparation

[hexed echo]

Yup

The statement

And application in problems

[mellow valve]

Trying to show that if what's in the green box is true, then the red box is also true.

No idea how to deal with the gcd(n,m) in denominator of 2nd term, basically hit a brick wall.

[lusty hornet]

i think it goes by this you do na- nb =n(a-b) then take the inverse of n mod m maybe you will get the red box. Try doing that way

[twin summit]

See that we have $m|n(a-b) \implies n(a-b)=m.c$, then $n_1.gcd(m,n).(a-b)= m_1.gcd(m,n).c \implies n_1.(a-b)=m_1.c$, where $gcd(m_1,n_1)=1$. Then, we have $m_1|(a-b) \implies \frac{m}{gcd(m,n)}|(a-b)$, which proves the statement.

[sterile pumice]

usernamephobic:

[tender light]

I simulate cramer's model and compare it with Li(x) and the prime counting function. I couldn't see the exact problem about cramer's model is not good for primes

[sacred junco]

https://asone.ai/polymath/index.php?title=Cramer's_random_model_for_the_primes

"This model is not perfectly accurate, because it neglects some obvious structure in the primes, for instance the fact that they are mostly odd"

[hexed echo]

Can anyone give me the proof of theorem 7 in the above document

Also give me a proof of theorem 6

[sacred junco]

proof of thrm 7 depends on complex analysis

[hexed echo]

I'm a tenth grade student only

I only know basic analysis stuff like limits, continuity, and completeness

[sacred junco]

rip

[hexed echo]

Even I don't know linear algebra

rip
@sacred junco why?

[sacred junco]

proof of thrm 7 depends on complex analysis

[hexed echo]

Ohhhhhh

Theorem6

Then

[sacred junco]

theres a simple proof of thrm 6

[hexed echo]

Which one, i.e., where can I find that

[fervent crest]

In Ireland, Rosen's "A Classical Introduction to Modern Number Theory"

[sacred junco]

bebe rudin

[fervent crest]

oh that's nice

[torn escarp]

what have you tried?

[sacred junco]

I'm not sure why that last inequality is less than or equal to 1

when could it ever be exactly 1?

That interval would have to miss an entire unit-length's worth of interval that would count towards another solution

The theorem the book is referring to is expression solutions to $ax+by=c$ as $(x_1 + kb/g, y_1 - ka/g)$ where $k$ is an integer and $g = \gcd(a,b)$

RIP TeXiT lol

[sacred junco]

Learning about column operations derived from the Euclidean algorithm to solve linear diophantine bois

this would be the same as row operations on the tranpose right

just to make sure I am not crazy

[cedar badger]

For this question, I am trying to prove that it is true. I have that as $p | (2n)^2 + 1$, we have that $4n^2 + 1 = ps$, which we can take mod 4 to give us $1 \equiv ps \pmod{4}$, but I'm not sure what the last step here is

[sterile pumice]

Liria ^(;,;)^:

[torn escarp]

it says prove or disprove

@cedar badger

[cedar badger]

Yea

[torn escarp]

so think through the cases, does this mean p=1 mod 4 or are there other possibilities

[cedar badger]

What do you mean?

I tried it witt just like the first 7 or 8 natural numbers and so far every prime seemed to work

[torn escarp]

well p*s=1 mod 4 could mean p=3 or p=1 mod 4

[cedar badger]

Oh

[torn escarp]

so you should focus on either proving p=3 mod 4 can't work, or look for a counterexample of that form

[cedar badger]

Hrmmm ok

Thank you

[torn escarp]

yup

[cedar badger]

Hrm

I'm still not getting anywhere; the ctwo cases are etiher p = s = 3 mod 4, or p = s = 1 mod 4 yea?

I tried looking for a counterexample and I don't get any numbers that you can take the square root of; i.e, for p = 3, s = 3, we get 2 = n^2, which doesn't work as n is an integer

And when I try to do it using p = (4x + 3), s = (4y + 3), and multiplying those together, I get 4xy + 3x + 3y + 2 = n^2?

Which wolfram says is not solvable in the integers anywasy, but uh iunno how to show that

[junior sapphire]

Any prime dividing (2n)^2+1 is odd. Rewrite it as (2n)^2 = - 1 mod p and use Lagrange's theorem.

[torn escarp]

@cedar badger have you seen Gaussian integers before?

[pearl jolt]

@cedar badger if you rewrite as (2n)^2 = -1 mod p, you know -1 is a quadratic residue mod p. then use Euler's Criterion to get (-1/p) = (-1)^((p - 1)/2). for that to be 1, you need p = 1 mod 4
yeah, I think this is a bit more elementary than gauss integer

[pearl jolt]

Euler's Criterion: odd prime p and coprime integer a let (a/p) be the Legendre symbol, so (a/p) = 1 if a is a quadratic residue mod p and -1 is not. then (a/p) = (-1)^((p - 1)/2) mod p

proof sketch: work mod p. by FLT a^(p - 1) = 1 so a^((p - 1)/2) is either 1 or -1. now if a is a quadratic residue, we have a = b^2 for some b, so a^((p - 1)/2) = b^(p - 1)/2 = 1. if a is not a quadratic residue, then there's no such b and so a^((p - 1)/2) = -1

[cedar badger]

Oh

@torn escarp yes, I've seen gaussian integers

@pearl jolt oh interesting

I know Euler's criterion but how on earth did you link that to this

[hexed echo]

👍

[fervent crest]

What is the smallest positive integer $c$ such that there exists integers $a,b$ with $\frac1{\sqrt{c}}=\frac1{\sqrt{a}}+\frac1{\sqrt{b}}$

[sterile pumice]

Whoever:

[fervent crest]

*distinct integers a,b

[fervent crest]

<@&681259820611141654>

[celest plinth]

1 🤔

[sage fern]

i was thinking that but how

[celest plinth]

a=b=4

[fervent crest]

distinct

[sage fern]

oh right

yes

[fervent crest]

i corrected myself afterward

[celest plinth]

it is at most 4 then

since 1/2 = 1/3 + 1/6

[fervent crest]

yeah that's what I have too

[celest plinth]

not many other possibilities left

[sage fern]

doesn't it have to be 4, given that it's gotta be a square number

[celest plinth]

doesn't have to be square

at least it's not obvious

[sage fern]

ohhh

i am a fool

[celest plinth]

square both sides, get
1/c = 1/a + 1/b + 2/√(ab)

[fervent crest]

so ab is a square

[celest plinth]

if c is not square, we still need ab to be a square

[sage fern]

sqrt(ab) = sqrt(bc) + sqrt(ac)

assume no common factor between a, b, c?

[celest plinth]

that is most definitely not true

[sage fern]

i am bad at maths

i just multiplied everything out, what's the problem

[fervent crest]

well if we want c to be minimal then there shouldn't be any common factor between a,b,c

but that doesn't really mean a,b don't have common factor, which will imply a,b are squares

[sage fern]

well obviously

i meant no common factor between all 3

[fervent crest]

yeah

[sage fern]

actually yeah you can just reduce it to 1/C = 1/A + 1/B, A < B wlog

but in the reals

so actually probs not helpful

[fervent crest]

lol

[sage fern]

i am bad at number theory

[supple furnace]

For a given positive integer c, the number of solutions is d(c’), where c’ denotes the largest perfect square factor of c.

I can supply the proof if you want

||Rewrite the relation as 1/sqrt(c)-1/sqrt(a)=1/sqrt(b) and square to deduce that ac is a square and similarly that bc is a square. Write c=kr^2 with r maximal. By construction, k is squarefree. Since ac=x^2 for some x, kc=(x/r)^2. However, k|x/r because k is squarefree and because each prime dividing k divides x/r. Hence x/r=kt for some t and so a=kt^2. Similarly b=ku^2 for some u. This reduces the relation to the well-known 1/r=1/t+1/u, which can be rewritten as (u-r)(t-r)=r^2. Clearly, t,u>r, and so u-r traverses the positive factors of r^2=c’.||

@fervent crest

[pearl jolt]

a solution with significantly less brain would be to test c = 1,2,3 and try and solve the quadratic sqrt(ab) = c + sqrt(c^2 + c(a + b)). if you WLOG a >= b then it's easy to see you have a limited amount of a and b to check, using the fact that these radicals must be squares to narrow them down more

[fervent crest]

@supple furnace what's d?

[supple furnace]

Number of divisors

@fervent crest

[fervent crest]

Ah ok

[vale snow]

I don't get it

like idk what they are asking and how to set it up

[sleek cove]

if a numbers last digit is 0 and the sum of all its digits is divisible by 3, which numbers 2-9 divide it

[vale snow]

ohhhhhhh

ok

ty

im so smart

[bleak matrix]

I found this interesting, if you multiply two binomials, e.i (x+b)(x+b) or just (x+b)^(2) and x is an odd number and b is even you can certainly find numbers that is a square of prime number. My conclusion is that there are many of this square-prime starting from 9, 25 and so on. So far I have no proof, (x+b)^(2)=p^(2). I know this is a witless conclusion and boring😅😆

[swift shard]

@bleak matrix
What? Can you give an example?

[stuck roost]

It's like you're looking at the expression $x+b=p$ and squaring both sides...

[sterile pumice]

Apopheniac:

[fervent crest]

I mean of course

If you substitute p into x^2 then of course you will get p^2

MAGIC

[swift shard]

I mean if you don't use a prime number and you get one, that's a neat result. But I'm suspecting one is used somewhere

[sleek cove]

no, they might be on to something

it even works with 3 binomials

[sage fern]

i have no idea what they're talking about

can you give an example

[sleek cove]

im joking, they're just saying that there exists odd x and even b such that (x+b)(x+b) = p^2

[swift shard]

Well, yes. That's definitely true haha

[sleek cove]

what if p = 0

[waxen jay]

among these sets how to identify which are vector subspaces

[lusty hornet]

This is the wrong channel . just check everyone out, you may know the definition of a vector subspace right

U is a subspace of V, a vector space over F , if it is a subset of V and it inherits the vector space structure from V

also you didn't specify subspaces of which vector space?

that isn't that important to know though

[cedar wagon]

aghh the best subject

[sacred junco]

Does anyone know how to count the number of integer solutions to an equation?

Specifically it is of the form

$$y^2 = x^a + b (mod p)$$

[sterile pumice]

doublemintdave:

[sacred junco]

Where p is a prime

[torn escarp]

any ideas

[sacred junco]

uh I'm thinking Legendre symbols

[torn escarp]

also specifically are you looking for x,y solutions for some fixed a,b

or just all x,y,a,b

[sacred junco]

a, b, p would be fixed

like the number of solutions as a function of a, b, and p

Since I guess this is really just, how many of x^a + b are quadratic residues

but no idea where to go from there

[torn escarp]

yeah

not sure either, but I think your idea for legendre symbols is probably a good place to look

[sacred junco]

sorry forgot to mention a does not divide p - 1

[torn escarp]

you could also fix a to be in {0,1,..., p-1}

oh

any more information

or can you just post a pic of the original problem

[sacred junco]

no that's the entire problem

[torn escarp]

well since a doesn't divide p-1 that means the set of {x^a | x in Z/pZ} = {x | x in Z/pZ}

since x^a |-> x is an injective map

that make sense?

legitimately asking cause I'm super tired right now lol

[sacred junco]

don't we need gcd = 1 for that?

[torn escarp]

yeah gcd(a, p-1)=1

[sacred junco]

well for example a = 4, p = 7

[torn escarp]

oh yeah good point @sacred junco

that's a shame then, cause it would have made the problem tractable I think

[sacred junco]

@torn escarp yeah that's an interesting idea, we could just argue that {x^d + a} is just a permutation of {x} and solve y^2 = x (mod p)

@dense oyster I think that's way too advanced for this problem, but thank you

it was just mentioned in class, it's not a homework or book problem or anything

I was just curious as to how to solve it

[torn escarp]

the restrictions make it seem like there's a known solution

it's too specific I think

[sacred junco]

it's a algebra/number theory class, undergrad level

[supple furnace]

There are explicit answers for some of the cubic cases, but they’re already extremely complicated

Unfortunately the divisibility doesn’t help much

Without gcd 1

[torn escarp]

maybe you can split into two cases for when b is or isn't a quadratic residue

[sacred junco]

hmm, maybe my professor said gcd(d, p - 1) = 1 and I misheard d does not divide p - 1

[torn escarp]

and factor a difference of squares

[sacred junco]

this was like 2 weeks ago

and he didn't write it down just said it out loud

[torn escarp]

it probably was gcd then, at least it makes the problem like super simple lol

[sacred junco]

yeah ok that makes sense, if it's gcd then it's just p right?

[torn escarp]

yeah

[fiery root]

I'm searching for this theorem online, but I'm just finding the normal division-based method and I can't figure out how to apply it here.. Any help, guys?

[sleek cove]

maybe try the euclidean algorithm instead of theorem

[lusty hornet]

@fiery root use congruence to solve it

[pearl jolt]

(x^a - 1, x^b - 1) = x^(a, b) - 1 by euclidean algorithm

[sly anvil]

that makes sense but how do you prove that by the euclidian algorithm

[fresh plover]

I guess this approach can be used

[fresh plover]

...

[leaden swan]

How do you show a solution exists for x^2+1=0(mod p) iff p=4k+1?

[abstract flax]

That's not true. x^2 + 1 = 0 (mod 10) has a solution of x = 3.

@leaden swan

[leaden swan]

p is prime

mb

[abstract flax]

Ah

An odd prime.

[muted breach]

If x satisfies x^2=-1 mod p then x has order 4 in (Z/pZ)^*. Since (Z/pZ)^* has order p-1, by Lagrange p-1 must be divisible by 4. For the other direction, (Z/pZ)^* is cyclic, so for any divisor of its order (p-1) it has an element of that order. In particular if p=4k+1, it has an element of order 4.

[leaden swan]

Ok, Thanks

[tribal granite]

If someone could help me with some parent function transformations it would mean so much (dm me)!

[sacred junco]

not really sure how to evaluate the sum involving the mobius function

i got that equation just from the formula for multiplying dirichlet series

[sacred junco]

look up möbius inversion formula

that inner sum is euler totient function

[sacred junco]

k will do thanks

[static sapphire]

Is there a good reason why the number (2+√3)^odd when written as m+n√3 has m one more than a square

[leaden swan]

Induction?

[static sapphire]

@leaden swan
I’ve already proven it by induction. It doesn’t give any insight into why you should expect it to work

[supple furnace]

Here’s that reason: We know that (2+sqrt(3))^odd=sqrt(3)^odd=sqrt(3) mod 2, so m is even. But we have that (m+nsqrt(3))(m-nsqrt(3))=((2+sqrt(3))(2-sqrt(3)))^n=1, so m^2-3n^2=1. Hence (m-1)(m+1)=3n^2, and so since m is even, m-1 and m+1 are relatively prime. This means that either m-1=3r^2 and m+1=s^2 or m+1=3r^2 and m-1=s^2. In the first case, we get s^2-3r^2=2, which is a contradiction mod 3, so the second case must hold, meaning m=s^2+1.

So we also get m=3r^2-1 as a bonus.

A similar argument shows that if (2+sqrt(3))^even=m+nsqrt(3), m=6r^2+1=2s^2-1

@static sapphire

[static sapphire]

I really appreciate the solution, it’s really elegant

[sterile pumice]

tree3:

[sterile pumice]

tree3:

[supple furnace]

Hope this is informative!

@static sapphire

[raven stag]

so like

I was solving this problem

"For each prime p. Find the number of primitive roots modulo p."

and I think I've solved it

but I checked out the solution and it was kinda similar but the formula was really different

and now I'm not sure if my solution is true

cuz it such equality seems really weird

like

lemme write up my solution in english and latex

but my formula was P-D(p-1) where D(p-1) is the number of divisors p-1 has

and the book's solution was phi(p-1)

I think there should be smth wrong with my solution

most probably

[sacred junco]

I think so too

[raven stag]

lol

[sleek cove]

D =/= totient function

[raven stag]

yeah Ik

but my formula is p-D(p-1)

[cedar badger]

where do I even begin with this lol

[sleek cove]

oh nvm

[raven stag]

wait lemme write up my sol

so that you can tell me where I got it wrong

@cedar badger I think that that's a peice of algebraic number theory

go to the more advanced channel Ig

[cedar badger]

o

[sleek cove]

iirc you need a fair bit of lemmas/other theorems to make the proof not like hella long

[sage fern]

i mean i see an obvious approach

hmm

it doesn't work

ignore me

wait, it might work?

yeah it works i think

the duality of man

really short too

i feel like i've gotten it wrong it's so short

[raven stag]

Let $q$ be an arbitrary primitive root modulo $p$. let $d_k$ be the kth divsor of p-1. \newline Now, we know that every residue class $q^{d_k}$ (with the exeption of when $d_k = 1$) is not a primitive root \newline cuz $(q^{d_k})^{\frac{p-1}{d_k}} \equiv 1 \mod{p}$. Lets define $D(p-1)$ as the number of divisors of $p-1$. \newline Then there are $D(p-1) - 1$ residue classes that are not primitive roots, and since we have $p-1$ residue clases, we have $p-1 -(D(p-1)-1) = p - D(p-1)$ primitive roots modulo p.

@sage fern what are you talking about?

[sage fern]

liria's thing

[raven stag]

okay

[sage fern]

yeah i shoulda been babbling in that other channel

[raven stag]

go on

Ig

what's wrong with textit?

[sage fern]

i hear it's just super super slow sometimes

[raven stag]

,tex Let $q$ be an arbitrary primitive root modulo $p$. let $d_k$ be the kth divsor of p-1. \newline Now, we know that every residue class $q^{d_k}$ (with the exeption of when $d_k = 1$) is not a primitive root \newline cuz $(q^{d_k})^{\frac{p-1}{d_k}} \equiv 1 \mod{p}$. Lets define $D(p-1)$ as the number of divisors of $p-1$. \newline Then there are $D(p-1) - 1$ residue classes that are not primitive roots, and since we have $p-1$ residue clases, we have $p-1 -(D(p-1)-1) = p - D(p-1)$ primitive roots modulo p.

okay

lol

[sage fern]

it'll probs pop up in like another 20 mins

[raven stag]

lol 20 mins?

oh

[sterile pumice]

Astrolopithecus43:

[sage fern]

ah there we are

[raven stag]

lol

so is that aproach correct?

Ig I might have gotten that last step wrong

this is the book I was talking about's proof

[sacred junco]

how do you know this is all of them?

wouldn't you only know there are at least that many?

[raven stag]

okay yeah you're right

I have to prove that that's all

lol it seems like the wrong aproach

[sacred junco]

you won't be able to prove that since it is not the right number

[raven stag]

okay

that means that

there exist a number t which is not a divisor of p-1, and that $(q^{t})^X \equiv 1 \mod{p}$

being X another number

but I think that this leads to a contradicction

isn't it?@sacred junco

[sacred junco]

I don't think it will but you can try

[sterile pumice]

Astrolopithecus43:

[raven stag]

no

like

oh okay

[bleak matrix]

I think this is the right place to put this problem.

Find all positive integers, such that n^(4)+4m^(4) is prime. I first tried the first case for n,m=1 which is prime, I don’t have any more idea where I can find any other cases. Where should i start?

[leaden swan]

Try to rewrite the equation as a^2-b^2 for some a,b

[bleak matrix]

I think it’s (n^(2)+2m^(2))^(2)?

[leaden swan]

Add and subtract 4m^2n^2

You get (n^2+2m^2)^2-(2mn)^2

[bleak matrix]

Where did 4m^(2)n^(2) came from?

@leaden swan

[leaden swan]

This

[sacred junco]

a^2+4b^2+25c^2=2ab+10bc+5ca, a,b,c integers

a,b,c =?

[leaden compass]

letting x = 2b, y = 5c we get

a^2 + x^2 + y^2 = ax + xy + ya
@sacred junco can you think of things to do with this now?

try to factorize things e.g.

there's a straightforward way: it involves a certain well known-inequality

[sacred junco]

i understand, now , thanks ! @leaden compass

[leaden compass]

np

[sacred junco]

this is a table for all the possible sums of the faces of 2 dice.

if I added a 3rd die, how could I count the number of times say 13 appears?

it sort of makes sense that I could fix the value of the 3rd die from 1 to 6, and see 13 sort of make it's way through the diagonals starting from the bottom right and ending at the center diagonal

but then what happens if I add another die? xP

[sage fern]

cube

[sacred junco]

https://www.mathpages.com/home/kmath093/kmath093.htm

I found this, seems quite complex

at least to me

[torn escarp]

yeah that's a good site

[sacred junco]

how would i evaluate $4x \equiv 5$ (mod 7)

[sterile pumice]

maddog

[leaden swan]

Multiply by 2 on both sides,you get x cong 3 (mod 7)

[sage fern]

solve bezout's equation to find the inverse of 4, 4^-1, then multiply both sides by 4^-1 to get x == 5(4^-1)

or yeah you could just see 4^-1 == 2

[bleak matrix]

Is there a book about elementary number theory, transition to advanced? I’m still in highschool and learning abstract algebra and number theory myself. Can anyone recommend me about a good book about elementary number theory?

[mild siren]

You could do a lot worse than to start with Silverman's "A Friendly Introduction to Number Theory"

[supple garden]

Hey how would you prove an upper bound for gcd(n,floor(n rt 2))

@raven stag what book is ghat?

That*

I realize that is a very crappy image my camera is quite terrible so if anyone want I can resend it

[raven stag]

you mean the book I send a pic of before?

well

that's OTIS expcerts

[supple garden]

Oh evan chen

[raven stag]

is a book on olympiad maths

yes

by evan

[supple garden]

Yea knew I have seen the format somewhere

[raven stag]

idk why I have the feel that I've seen you in another discord

do you recognize me?

[supple garden]

The Olympiad math one?

[raven stag]

my pfp

no

another one

lol idk

do you recognize the guy in my pfp?

[supple garden]

Yea you and I have 2 mutual servers

Interesting stuff

I am doing number theory as well currently