elementary-number-theory

[hoary shell]

No I just gave up

[jagged narwhal]

idk how accidently i came here.

but fine

[sterile pumice]

Vanellope von Schmugz

[hoary shell]

No. I just gave the problem to my bf

He said trivial and moved on

[rugged locust]

do you want the short answer or the long answer... lol

[rugged locust]

so short answer then

short answer is solving the equation in the form S=0 is how you avoid accidentally dividing by zero divisors

you could do that, I wouldn't do that. also it doesn't work if a common factor only exists on one side

[sterile pumice]

Vanellope von Schmugz

[hoary shell]

When you are expressing n and m as 2k+1 and 2m+1 for example. Aren't you assuming m and n can be divisible by 3?

[charred roost]

It doesn't matter whether m and n are divisible by 3. The implication you're proving is that if m and n are odd then n^2 - m^2 is divisible by 8, which is true no matter what n and m are modulo 3. The assumption that m and n are not divisible by 3 only comes into play when you're proving that n^2 - m^2 is divisible by 3.

[hoary shell]

Is there an easy way to show 2^644 is 1 mod 645 without fermat little theorem

[patent acorn]

you could compute 2^644 mod 3, mod 5, and mod 43, using repeated squaring or whatever, and then use the chinese remainder theorem, i guess

...is there a particular reason you don't want to use fermat's little theorem?

[patent acorn]

ok wait this is fairly easy actually
mod 3, 2^644 = 4^322 = 1^322 = 1
mod 5, 2^644 = 16^172 = 1^172 = 1
mod 43, 2^7 = 128 = 3*43 - 1 = -1, so 2^644 = (-1)^92 = 1^46 = 1

[hoary shell]

Dumb requirements otherwise i wouldn't be asking

[hoary shell]

How do you prove if 11...1 (n times) is divisible by 41 iff n is divisible by 5?
I tried playing around with examples but nothing so far

[rugged locust]

I really doubt it

I guess if you really wanted to avoid flt, you can use crt instead and brute force compute 645 = 3*5*43

[surreal crescent]

What does Fermat’s little theorem have to do with it

[rugged locust]

Well, 645 is not prime so it’s technically not an application of Fermats little theorem but the Euler Fermat theorem

[rugged locust]

Actually yeah, that is a good point, you can’t even use fermats little theorem here

[long lion]

i mean, u could split 645 into 3*5*43 then apply FLT & CRT

[long lion]

you can prove (10^n - 1)/9 = 0 mod 41 iff 5 ! n

or like another way u could approach it is i.e. 1111111111 = 100001 x 11111

and 11111 is always divisible by 41

[hoary shell]

Yeah figured

Stuff like this simplifies so easily when I use abstract algebra

[fresh galleon]

i was discussing this in the other server with someone and was wondering how we could continue with proving the 3 questions listed (the other person proposed the question, not me)

[surreal crescent]

<@&268886789983436800> this is a current SUMAC application problem. don’t fall for the “I’m asking for my friend” idea I wouldn’t trust that

[nimble owl]

@fresh galleon ^

[fresh galleon]

oh i did not know that wtf

ok i’ll ban/mute the other person in the server thanks for telling me

[fresh galleon]

sry i didn’t know

i’m just a curious guy cause it seemed like such a nice NT problem

[surreal crescent]

I think it’s slightly odd u made sure to specify that it was the other person who proposed it

u should probably delete it here

[surreal crescent]

🤷‍♂️ I don’t think it’s that nice but whatever

[fresh galleon]

i physically cannot due to my old phone

[fresh galleon]

😔

[fresh galleon]

i’ll be back home in a few hrs so i’ll delete it then

[untold osprey]

Anybody have a free resource for me to learn number theory

[still flare]

If you google "number theory pdf" you will find many free textbooks. There ought to be a list of textbooks in #book-recommendations which, if you google with the word "pdf" you will probably also find.

I can't possibly support piracy. Pity it's so easy.

[untold osprey]

Found a bunch. Thank you. Just out of curiosity: Do you have a favorite number theory textbook? Let me know if you do, I'll ethically get my hands on it

[still flare]

I can't say I do I'm afraid

[untold osprey]

No problem, thank you again

[quaint gate]

sure https://www.math.gordon.edu/ntic/nticoneside.pdf

[sterile pumice]

victor

[sterile pumice]

Please give me something to compile, for example latex ,tex The solutions to \(x^2 = 1\) are \(x = \pm 1\).See ,help and ,help tex for detailed usage and further examples!

Jan 30, 2025, 11:47 PM

[forest plank]

Interesting problem 🤔 if m is coprime to 3, then seems easy. But if divisible by 3, then I have no idea 😭😭

[slim vortex]

heh, I have the opposite intuition

but I don’t see it either way

[forest plank]

If m is coprime to 3.

Split the set of all the 3-subsets into equivalence classes like this: if we have {a,b,c} then its class is all the sets {a+k,b+k,c+k} for k from 1 to m (reduce modulo m when necessary).

So, in each class there are exactly m members. Also, the sum will have the form a+b+c+3k, and since 3 is coprime to m, it will go through all the possible remainders modulo m exactly once.

And.. that's basically it. Done.

For m divisible by 3 this argument won't work though.

[long lion]

<@&268886789983436800> spam

[foggy granite]

Hello! I am tasked with solving this problem, but I am stuck on what to start with. Any help would be appreciated!

this my starting attempt at (a).

[deep chasm]

Does anyone know how I would find the multiplicative inverse to: $n , mod(2n+1)$

[sterile pumice]

Embeddedmonk20

[loud maple]

Hint: 2n ≡ -1 mod (2n+1)

[long lion]

right so you have this ugly quadratic

one of the roots you already know is x=1

use that to find the other root

[queen frigate]

can someone look at help-35

[lavish river]

I'm stuck on b) here

I can see that the sum over divisors d of m of phi(d) is equal to the sum over divisors d of m of the number of elements of the group of units with respect to d, but I'm not sure why that's equal to m

[lavish river]

ah nvm I think I solved it.

[clear lily]

hello
I'm looking for another beginner in number theory who wants to learn with me, share ideas, and help each other when we get stuck on a problem. I'm studying from the book Number Theory (Pure and Applied Undergraduate Texts) by Robert Freud, which I personally find quite challenging. If somebody would recommed another book, please let me know.

I’m not looking for someone who already knows most of the solutions but rather someone who is genuinely interested and who wants to learn together sometime. Since I’m still in high school, I’m not very advanced, so I don’t want to slow anyone down who prefers a faster pace.
I’d love to study in the evenings (GMT+1), around 2–4 times per week, but if because of various reasons, someone can’t meet regularly, that doesn’t matter for me. If anyone is interested, please let me know!
Kind Regard

[rugged locust]

hi! I already know NT, but I would love to just talk about it with you.

dm me if you ever have any questions :)

[clear lily]

thank you very much!

[swift finch]

https://www.youtube.com/watch?v=Jv1zpi9zuZ4https://www.youtube.com/watch?v=Jv1zpi9zuZ4

What are your thoughts on this video

[dark kraken]

Ok, so I had a complex problem that I managed to boil down a lot. Essentially, I need to know the union of the events that n(n-1)(n-2)(n-3)(n-4)(n-5)(n-6) are divisible by 2^6 and the event it is divisible by 3^3. He said we could use a smaller class than 2^6*3^3 to calculate this, but I am not aware of how to do this. Anybody have any ideas?

I know that the magic modulus is 24 and that the union should have a probability of 23/24. Anybody know how I can get this?

[forest plank]

Easy to see that divisibility by 3^3 is determined by the remainder of n modulo 9.

Notice that the expression will always have at least two numbers divisible by 3. If there are 3 such numbers, or if one of them is divisible by 9, then the whole thing is divisible by 3^3.

So the only way it isn't divisible by 3^3 is if n = 7 or 8 mod 9. Probability = 2/9

Then need to do similar analysis for divisibility by 2^6.

Obviously if n even, then divisible. By then examining all possibilities mod 8, you get that it's definitely divisible if n = 1,5 mod 8.

So we have only cases n = 3,7 mod 8 left. If 7, then definitely not divisible. If 3, then potentially can be divisible. So, we now need to consider mod 16 to be sure. If 3 mod 16, then divisible. If 11 mod 16, then not divisible.

So, in conclusion, not divisible if n = 7, 11, 15 mod 16. Prob = 3/16.

2 and 3 are coprime, so divisibility by their powers are independent events, so prob of not divisible by neither 2^6 nor 3^3 is 2/9 × 3/16 = 1/24.

[dark kraken]

interesting, thank you! how did you decide on mod 8 for the case for 2?

[forest plank]

Intuition

[random lantern]

im wondering if this is enough for a proof of if you have 3 consecutive numbers n n+1 and n+2, one must be divisbile by 3. basically im saying suppose n = 1 (mod3), then n+1 = 2(mod3) then n+2=0(mod3)

[still flare]

Yeah sure, you can argue that n is one of 0, 1, or 2 mod 3, and then you can check that if n == 0 mod 3 you're done, if n == 1 then n+2 == 0 mod 3, if n == 2 then n+1 == 0 mod 3, so in any circumstance you're done.

This is the most straightforward proof I can imagine

[surreal crescent]

or just like pigeonhole principle kinda

[random lantern]

ok, tyvm

[dark kraken]

i've boiled down my question a bit. So if we take n(n-1)(n-2)(n-3)(n-4)(n-5)(n-6), we know if n is even, then we're guaranteed to have 2^6 as a divisor. so, n can be of the form 2k. If we have n odd, we can consider only the terms (n-1)(n-3)(n-5) as multiples of 2. We can rewrite this as 8k(k-1)(k-2). If the middle term is even, we know that n has to be of the form 16m+3. Now if the two outer factors are even, we know that one of them has to be a multiple of 4. i'm trying to figure out how to determine the form that n would need to be in for this case

my thought was that we'd be guaranteeed to have a factor of 2^6 in that case so any 2m+1 would work, but i know the answer is only 4k+1

[dark kraken]

figured it ou!

[modest coral]

how can i show that if k is not a multiple of s/gcd(r,s), then rk is not a multiple of s?

or the contrapositive

the original problem is in #help-22

[modest coral]

it's now in #help-44｜stanley-🌲-v2-dans

[foggy granite]

Hello! Not sure how to approach this problem. Any guidance would be appreciated!

[forest plank]

Ok these are equivalent to...
x + 7y = 14
-5y + z = -8

x = 14 - 7y
z = -8 + 5y
So uhmm.. x,z are determined by y, and y can be any integer. 🤔

Yeah, matches with intuition. This is 2 planes, their intersection is a line that can be, turns out, parametrized by y.

[cold olive]

Hope this help.

[foggy granite]

Thank you! I will look it over in the morning.

[tough edge]

How can you show that 2a^2 + 3b^2 = 4c^2 has no natural number solutions

[torpid charm]

$2a^2 + 3b^2 = 4c^2$

[sterile pumice]

mixolydian mode

[loud maple]

x² can only be 0 or 1 mod 3.
4c²-2a² = 3b² ≡ 0 mod 3
This is only possible when c and a are both 0 mod 3. Write a=3m and c=3n. Now divide the original equation throughout by 3

From this point on it should be trivial

[tough edge]

ohh i see

[runic raptor]

How to solve it ?

[torn escarp]

little thing called binomial theorem

[vapid elbow]

<@&268886789983436800>

[dawn osprey]

just a q: cant we use l'Hôptial's rule?

[torn escarp]

it's your life

really this question is probably just asked in the wrong channel since what I see when I see this question is not a real analysis question at all

[rugged locust]

you get what you ask for, post in NT channel, so people tell you to use binomial theorem

[long lion]

i mean, i guess that's sort-of circular

since the limit is effectively the derivative of x^n at 1

[unkempt void]

Ye

[silver thorn]

This is the derivative of (1+x)^n at x = 0 by definition

[silver thorn]

You could, but that's circular reasoning

[silver thorn]

And here's why

[torn escarp]

the fact that I got a heart here means I failed to send the correct message here lol

it was not an endorsement it was to make you question your life choices

[hoary shell]

For which values of n is 3^n+2^ div by 13?

[hoary shell]

From just messing around it seems to me that n = 2 mod 12, n=6 mod 12 and n=10 mod 12

Are there any more? If not how do you prove that's it?

[rugged locust]

Also do you mean mod 13?

[hoary shell]

mod 12

[rugged locust]

So then you mean 12 here?

Because they don’t add up

[hoary shell]

It's 13 here

[rugged locust]

…what

[hoary shell]

I think I got it but correct me if I'm wrong

From FLT, 2^12 = 3^12 = 1 mod 13

so we can use these as the identity

[rugged locust]

Oh, you already applied flt gotcha

[hoary shell]

now we have 2^(12+n)+3^(12+n) = 0 mod 13

[rugged locust]

Yeah in that case it checks out

[hoary shell]

[lunar creek]

is this rational for any positive integers a, b, c, d (ofc all different)

*this comes paired with the condition

[regal summit]

No

a = 16, b = 33, c = 63, d = 56

[lunar creek]

damn

the question I have has more conditions but I figured if there's a way to show it with just that then I wouldn't need to worry about all the other conditions

[hoary shell]

If a prime p = 3 mod 4, how to show it nevers divides a number of the form n^2+1?

[long lion]

sps n^2 = -1 mod p

then square both sides to get n^4 = 1 mod p

can you use fermat's little theorem from here to get a contradiction?

[shy geyser]

The theorem that states:
"Being n a Natural Number. If 2^n - 1 is prime, then n is prime."

Could be generalized to:
"Being a a Real Number and n a Natural Number. If a^n - 1 is prime, then n is prime"?

[patent acorn]

no

it's extremely easy to come up with counterexamples to that, if a can be an arbitrary real number

[hoary shell]

Yeah figured

If we want to show 2^(12+n) + 3^(12+n) = 0 mod 13, we check for n mod 12 but is there a way to make this calculation less miserable?

[rugged locust]

I mean, you can just directly get rid of the two 12's via flt no?

[hoary shell]

wdym

[rugged locust]

fermat's little theorem

[hoary shell]

Yeah where

[long lion]

2^12 = 1 mod 13, so 2^(12+n) = 2^n mod 13

[rugged locust]

2^(12+n) = 2^12 * 2^n = 1 * 2^n = 2^n

[hoary shell]

So we check 2^n + 3^n = 0 mod 13 for n (mod 12)?

[long lion]

yeah

probably gonna be a bit of a miserable calculation but oh well

[hoary shell]

That is still horrible

oh shit well

[long lion]

oh wait ignore me

we want 2^n = -3^n mod 13

so (2/3)^n = -1 mod 13

and then you just need to work with 2/3 instead

also may i ask what ur mathematical journey was that lead to u studying CFT before elementary NT lol

[hoary shell]

I'm just trying to find simple ways of solving these without overkilling

I'm teaching kids

[long lion]

ah right ic

[long lion]

yeah in which case probably just bash it

[hoary shell]

I feel so sorry for the kids

[long lion]

don't be, they'll have to learn how to be the grad student eventually

[hoary shell]

I'm just sleepy rn but wouldnt that work for p = 1 mod 4

[rugged locust]

here's a hint - the equation n^2 = -1 mod p has solutions exactly when p = 1 mod 4 (and 2)

[hoary shell]

Yeah I know I think I came up with a pedagogical way to think about this

It will make the kids appreciate Lagrange's theorem even if they don't know about it

[rugged locust]

lol, good luck with that

[bold anvil]

given $a,b\in\mathbb{Z}$, how is it true that both $\frac a{a^2-b^2}$ and $\frac b{a^2-b^2}$ are integers only if $a^2-b^2=\pm 1$

[bold anvil]

how does it boil down to $a^2-b^2=\pm 1$

[bold anvil]

well for both of these to be integers , it must be true that $a^2-b^2|a$ and $a^2-b^2|b$ so the inequalities $a^2-b^2\leq a$ and $a^2-b^2\leq b$ should both be satisfied

[bold anvil]

the professor only said that this is the case because |a^2-b^2|>=a and |a^2-b^2|>=b but idk how that gives this conclusion

[bold anvil]

ohhh wait a sec

[bold anvil]

if both of these must be integers

then there sum must be an integer and so should there subtraction

which means that $\frac 1{a+b}$ and $\frac 1{a-b}$ must be integers

[bold anvil]

but this isnt possible unless a+b=1 and a-b=-1 which gives a=0, b=1, or it should be a+b=-1 and a-b=1 which gives a=0,b=-1

also the values of a and b can be swapped

which gives a=1,b=0 and a=-1, b=0

[bold anvil]

although this doesnt have any relation with this

at least there is no relation that i can see

if this is related then i would like to know how

[long lion]

approach could work, although i don't see why this would be a good approach

[long lion]

this feels like the much easier approach

[bold anvil]

yes but now i am curious to know how this leads to the conclusion (if it does)

[long lion]

as in possibly? but i can't see like some 1 liner solution that immediately implies a^2 - b^2 = +-1

[still flare]

Give it the name x = a^2 - b^2 = (a+b)(a-b). I am going to assume neither of these factors are 0 (you seem to have assumed this implicitly). Since x | a and x | b, we know x | a+b. You can then conclude that a-b = +-1 (can you see why?). Similarly x | a-b so we get a+b = +-1.

[long lion]

yeah that's what they did like

[long lion]

^ here

[long lion]

but apparently their professor wrote this and then wrote => a^2 - b^2 = +- 1

tbh idk why their professor would go down that route, i don't see why it's immediate why what they've written up there => a^2 - b^2 = +- 1, especially since that still doesn't tell you what a&b are

[long lion]

and bcus this is just like infinitely better lol

[still flare]

Ur right this is the same argument. My bad, I honestly didn’t see above

[lavish river]

I'm given that a function f is identically 0 modulo m, and that m' | m, I want to show that f is identically 0 modulo m'.

if I take an arbitrary x in Z/m'Z, does it make sense to say that f(x) = 0 mod m?

I'm skeptical because obviously the equivalence class x in Z/m'Z is not the same as the one in Z/mZ, but I'm not sure how to phrase something similar that is correct

oh wait maybe I can dodge all this equivalence class business.
take any integer x. f(x) = 0 mod m = km', thus f(x) = 0 mod m'. therefore, if x is in Z/m'Z, f(x) = 0 in Z/m'Z

I think this solution is correct, but if it's not or there's any commentary on this topic it would still be appreciated

[uneven flint]

I mean, f(x) = 0 mod m --> m | f(x) --> m' | f(x)

[still flare]

You are really asking if m | x implies m' | x.

The function is irrelevant

[bold anvil]

np dw about it

[bold anvil]

nvm the way that we all did is much better ( assuming that what the professor wrote leads to a way lol)

[shut flax]

I'm not too sure if this is the right place to ask, I was just messing around with the totient function and was wondering if for prime p there exists q, which is also prime, where p<q<p^2 such that q≡1mod p

I honestly didn't check to see how far it holds so there might be a small counterexample

damn that was fast

[patent acorn]

i think it's probably true but i have no idea how you'd prove it

[shut flax]

😔

[torn escarp]

I think you can even get infinitely many even from Dirichlet's theorem

[patent acorn]

there are infinitely many primes q with p < q < p^2?

[torn escarp]

heh 😛

[shut flax]

damn didnt know there were infinitely many primes between p and p^2 that's a lot

in any case its related to A061026 so ill have to bang my head against the door trying to read up on some of those links

[torn escarp]

there aren't lol just typing while not awake 🤣

I guess what other tricks are there to try in this area, some kinda cyclotomic polynomial thing?

I'll have to revisit this when I'm actually awake tomorrow maybe lol

[torn escarp]

but maybe this helps get started with an idea for an approach if you know what I mean vaguely but I'm definitely retiring to bed right now so good luck lol

[dusty dragon]

this appears to still be an open problem

here's a related oeis entry: https://oeis.org/A035095

related mathoverflow entry: https://mathoverflow.net/questions/80865/least-prime-in-a-arithmetic-progression

[shut flax]

😦

I'm a bit suprised that p<c*q^5.2 was the best unconditional I don't know why but I thought it would be at least 4 or lower

[shut flax]

Somewhat related, would it be true to say for https://oeis.org/A061026/ (a(n) = Smallest number m such that phi(m) is divisible by n, where phi = Euler totient function) that for prime p, a(p)=q, that q must be prime?

My reasoning so far has been if we use https://oeis.org/A001088 (Product of totient function: T(n) = Product_{k=1..n} phi(k)), and simple property is that T(n)=T(n-1)phi(n). So if we assume p does not divide T(n-1) but divides T(n), then p divides phi(n), but if n is composite then there is ab=n with gcd(a,b)=1 which would imply phi(a)phi(b)=phi(n), but since a and b <n then phi(a) and phi(b) divide T(n-1) which would be a contradiction since p would have to divide either phi(a) or phi(b) but not T(n-1), so n cannot be composite

[primal escarp]

You also have to check the prime power case, no? Because then you can’t factor as you claim

[shut flax]

I unfortunately realized that as I was going to bed last night :/

it's the way she goes

[loud maple]

2^m=n²-m²=(n+m)(n-m)
Now consider the prime factorisations of the two sides

[solar mortar]

we used to solve this kind of problems in olympiad
good days

[past spire]

I'm doing math olympiad right now lol

Which one were you doing?

[foggy granite]

Stuck trying to prove the case where n \neq 1. Any hints would be appreciated!

sorry, there is a typo in the question! should be $1, n=1$ and $0, n\neq 1$

[sterile pumice]

Vic

[long lion]

hint: LHS is a multiplicative function, so suffices to check it for n = p^k

[foggy granite]

this is where i got with your hint. am i on the right track?

[long lion]

mu(p^2) != mu(p)

as in yeah if you sub n=p^k then you can compute it explicitly

[foggy granite]

oh i think i see

one moment

so, something like this?

[long lion]

yh

that works

[foggy granite]

excellent. now to write it in a proof format

thank you!

[long lion]

nw

[forest plank]

Without multiplicativity:

The sum is actually over all square free divisors of n.

Say n has k distinct prime divisors. So, there are 2^k square free divisors.

And the sum can be reformulated as the sum over all subsets of a k element set, +1 if subset has even number of elements, -1 if odd.

Also, not hard to see that this sum is equal to (1-1)(1-1)(1-1)...(1-1) = (1-1)^k which is obviously equal to 0. (Each of the k parentheses corresponds to a prime divisor of n. When building a square free divisor, you choose 1 if you don't include a prime, -1 if you include the prime)

[shy geyser]

How is this proving that for all integer base we could represent every integer? I don't understand how it comes from the string to conclude that.

[weary rune]

if we didn't have that restriction

we could write 11 as 1*10+1*1 or 11*1

[lavish river]

I must show that if p = 2 mod 3, then all units modulo p are cubes

I honestly don't think I've tried anything useful. I wrote it out to check for p = 5 and 11 to see that it is true in those cases

[lavish river]

hm ok so I think we need to use the fact that the units modulo p contain a primitive root

if we consider the map x -> x^3 on (Z/pZ)*, then maybe we can show this is injective or surjective

[lavish river]

ok so we know that 3 is invertible mod p-1, i.e. we can construct a bijection k -> 3k on Z/p-1Z. does this imply there is a bijection g^k -> g^3k in (Z/pZ)*?

[surreal crescent]

that is a very good question. think about why we can express any positive integer we want in base 2 and then generalize

[silver oak]

we can represent every integer if there was no restriction, just let it be a0

with restriction you can always add 1 to anything, i don't know, there's no simple reason

if you specifically mean "why it becomes unique" that's even harder

[forest plank]

By euclidean division. (For any integer n and non-zero b we have n = bq+r where r less than b, and q,r are unique)

So, given an integer and base, a unique string is produced by repeatedly dividing by b and taking the remainder.

For example, let's take 137 and base 10.

137 = 10×13 + 7
13 = 10×1 + 3
1 = 10×0 + 1

[forest plank]

Let x be a unit. By Fermat's little theorem,

x^(p-1) = 1 (p)
x^(2p-2) = 1 (p)
x^(2p-1) = x (p)

We know p = 3k+2, so

x^(6k+3) = x^(2k+1) ^3 = x (p)

Thus x is a cubic residue

[lavish river]

I'm not sure what a cubic residue is but I think my proof ended up working

I'm not certain this is the best channel for this but I want to show that all real numbers in [0,1] can be written in a base 3 expansion (using 0,1, and 2)

does this mean I should show that we can write a = sum of a_n/3^n for a_n = 0,1,2?

ok so firstly, we know either
0 <= a < 1/3, 1/3 <= a < 2/3, or 2/3 <= a < 1 (a = 1 is trivial)
this determines a_1, since respectively we have
a = 0 + alpha, a = 1/3 + alpha, or a = 2/3 + alpha, where 0 <= alpha < 1/3

then we can somehow repeat this process for each a_n

ah I think I figured it out inductively

[idle locust]

Not sure how complex this is but it stumped me, say i have two numbers a and b, is there some way i can determine which of a^-1 mod n and b^-1 mod n is bigger? Assume inverses exist

e.g. if there was some expression f(a, b) where f(a, b) < 0 implied a^-1 > b^-1 and vice versa for f(a,b) > 0

[long lion]

wdym by bigger? remember mod n, concepts of size don't really exist bcus -1 = n-1 = etc.

if u mean which one is bigger when you reduce it to 0 <= _ < n, then i don't know of some easy way to do that unfortunately

[idle locust]

This, yes

[hoary shell]

Am I going insane why $a^{\phi(p)/2} \equiv 1$ (mod p)?

[sterile pumice]

Ring

[hoary shell]

when p = 1 mod 4

[forest plank]

If p is prime then a^... is equal to the Legendre symbol of a. So not always 1

For example p=5, a=2

[hoary shell]

a is a primitive root btw

[forest plank]

It should be -1 then

[hoary shell]

nvm figured it out

[shut flax]

I have a question, does anyone know if this inequality is true? For prime p>7, there exists composite n, where p<n<2p, such that phi(p)<phi(n), where phi(n) is Euler's Totient Function. Example, phi(11)<phi(21), phi(13)<phi(17)<phi(19)<phi(25), phi(23)<phi(35), phi(29)<phi(49), phi(43)<phi(65), phi(47)<phi(77), phi(61)<phi(85), etc. I've only looked at some values for under 100 so it might not be true

[surreal crescent]

yes that’s of course true

think why

[hoary shell]

Suppose there is an r such that r^(phi(n)/q) =/= 1 mod n for all prime divisors of n. Show that a is a primitive root.

How do you show this? I tried going by cases with the primitive root theorem but I'm lost

I'm supposing there is an easier way

I guess one of my question is why showing it for prime divisors suffices?

[still flare]

So you know why it works if we replace prime divisors with just divisors, and you're asking why we can replace with prime?

You will also have to assume r is coprime to n otherwise we will have some very silly counterexamples...

[hoary shell]

Yes

Is it because of the primitive root theorem?

No that's not it

Yeah idk why sorry

[still flare]

Hint: if r^x = 1 mod n, then x divides phi(n).

[hoary shell]

yes

[still flare]

Well actually sorry this isn't right

We need x to be the smallest such number

i.e., the order of r

[hoary shell]

so x has divisors as candidates

[still flare]

Exactly

And divisors of phi(n) are precisely phi(n)/y for some divisor y of phi(n)

But here's the trick

We can always choose the biggest things of that form, if you see what I'm saying?

If x divides phi(n) and isn't phi(n)....

I leave you to think about this now

[hoary shell]

I can see what you are trying to say but I can't seem to formulate it

[hoary shell]

why x can't be phi(n)?

it can right

[still flare]

Well if the order of r is phi(n), what does that mean about r?

[hoary shell]

Order of r is equal to phi(n)? Lol

[still flare]

No

OK you edited it, sure

But what are we trying to prove again?

[hoary shell]

a is primitive

[still flare]

you mean r is primitive, btw

[hoary shell]

oh wait

[still flare]

So when is r primitive

[hoary shell]

Yeah r is primitive

[still flare]

What does it mean to be primitive

[hoary shell]

Order of r is phi(n)

[still flare]

Yes.

So we can ignore that case, yes

Since we win immediately

I'm again going to leave you to think about this

[hoary shell]

yeah if the order of r phi(n) then r is primitive

Order of r is not of the form phi(n)/q for a divisor >=2

@still flare ok how about this.
Assume r is not primitive.
so k = order(r) < phi(n).
and k|phi(n). So there exist at least one prime divisor q of phi(n) s.t k divides phi(n)/q.

We can rewrite phi(n)/q = mk for some k.
Now a^(phi(n)/q) = a^(mk) = (a^k)^m.
Since a^k = 1 mod n
(a^k)^m = 1 mod n so a^(phi(n)/q) = 1. Contradiction

[shut flax]

That's why I'm asking. I'm 99% sure it's true for but I'm honestly having a difficult time thinking of how to prove it. If n could be prime then it's trivial, so n being an odd semiprime seem like the best place to start but not every odd semiprime between p and 2p satisfies phi(n)>phi(p) so that's not good enough. I can think of simple properties n must satisfy, but I'm pretty stumped on it

which is unfortunate because I mainly want a lower bound

if it turns out it's fairly simple that'll be pretty funny

[surreal crescent]

there’s always a prime between n and 2n

[shut flax]

Yes that's why i said trivial, and it can also be concluded there exists a natural number n such that p<n<2p, but what I'm asking though is that there exists a non-prime n with the property of phi(n)>phi(p)

I have an idea though now, I was trying to start from p but maybe I start from n instead

Let phi(n)/n>1/2, then every prime on the interval (n/2,phi(n)) satisfies phi(n)>phi(p)

[forest plank]

Hmm I think this is true. There's a generalization of Bertrand postulate that says that for any e>0, starting from some point, you can always find a prime between n and n(1+e).

So, given a (large enough) p, we find another prime q that is between sqrt(3/2 p) and sqrt(2p).

So q^2 will be between 3/2 p and 2p. And phi(q^2) = q^2 - q which should be bigger than p, I think.. 🤔

And after that just need to check everything for small p.

[surreal crescent]

ohhh I’m sorry

[surreal crescent]

i didnt realize it said n is composite. if it didnt have to be then its trivial

[thick panther]

diamond shurman exc 1.2.2, second part of (a)
i don't believe that the hint makes sense; how can a prime be 1 mod gcd(c,d) but 0 mod c?
what would the corrected hint be

[wild bluff]

Where can i find a similar definition?

adiccion

@everyone

[weary rune]

rule number one of discord:

do NOT ping or attempt to ping everyone in a large server

[swift quarry]

Does anyone know how I'd be able to do these questions? For a) I thought i was on the right track but it doesnt look like the examples given on the problem sheet

[weary rune]

what’s the largest power of 7 that is less than 799?

[regal summit]

7^3

[torn escarp]

!noans

[rotund gust]

The purpose of this server is to help you learn, not to hand out answers. Do not ask someone to give you the answer directly.

[regal summit]

oh cmon this question is not difficult

you check cases

[torn escarp]

I suggest using log and floor to get there instead

Working that way we can write down a more general solution to the more general problem for funsies:

What's the largest power of b that is less than c?

[swift quarry]

I understand it's 7^3 but then 799= 7^3 + 456 and im stuck from there

When I split 456= 7^3 +113 it doesnt easily become a power of 7 so ik I'm definetly doing it wrong lmao im really sorry

[weary rune]

divide 799 by 7^3

the quotient is your leading digit, now divide the remainder by 7^2

etc

[swift quarry]

Oh my god thank you

[weary rune]

npnp

[visual tree]

Oh cmon

[placid stratus]

👀

[torn escarp]

Random graphs without context are not interesting

[placid stratus]

I think graphs can be interesting even without context, particularly when the result is a smooth ovoid from primes as inputs, but dismissive attitudes are definitely not interesting

It's not like I just discovered a harmonic signal in the primes that can be used to predict them, or anything!

Sleeping for now, might share code tomorrow

[forest plank]

We're waiting 😊😊😊

[regal summit]

Oh brother not this shit again

[placid stratus]

You know, there is actually no incentive to share results with dismissive persons, never mind

If anyone is genuinely interested and doesn't just want to be rude, maybe

"Not interesting" + "Not this shit again" -> bye

Very toxic.

[graceful inlet]

#combinatorial-structures on their way to disagree

[regal summit]

Its bc people come in here acting like they solved an unsolved problem

Using a curve

Like i promise you that you didnt

[placid stratus]

I showed graphs and a one sentence summary

The results are very surprising to me because I did not expect symmetry and I did not expect a smooth ovoid if you only graph primes

I'm just really uninterested in people that react to sharing initial results of interest as you did

[regal summit]

Well having elliptic curves be a relevant part of a number theory discovery is pretty expected nowadays

Still pretty cool

But unfortunately it doesn't predict the primes

[placid stratus]

Composites are very unlikely to fall on the curve

I'm expecting it can be like primality tests based on Fermat's Little Theorem

[regal summit]

Well sure, but that "unlikely" part is still problematic

[placid stratus]

So if you want to check if a number is likely prime, you can check if it's on/near the curve

[regal summit]

We have plenty of probabilistic methods for primes

[placid stratus]

And they're all interesting

[regal summit]

But we are looking for a definite method

[placid stratus]

I never said I'm looking for a definite method

[regal summit]

I see

[placid stratus]

There are likely other applications

That's just an obvious one

[regal summit]

Well then you've actually likely stumbled across something potentially viable

[placid stratus]

Also it'll probably be way more useful than existing primality checks because you can stack the checks

A prime will be on every curve

You can generate as many curves as you want

[regal summit]

I just misinterpreted, thinking that you were claiming to have found a determiner of primes

[placid stratus]

The odds of a composite number being on increasing numbers of curves become vanishingly small

And this is not even the most interesting thing honestly

[placid stratus]

This thing is symmetric for no reason

I mean, the fact that you get smooth ovoids on primes alone is bizarre

[regal summit]

Well there's gotta be a reason

[graceful inlet]

Just saying, but I don't see that summary. What is it a graph of?

[regal summit]

Probably an elliptic curve primality test

[placid stratus]

I'm a little nervous to share because I guess I want to give myself a chance to try to prove some part somewhere before real mathematicians go off and get all the credit

Maybe write a little paper

But this is a very simple operation, actually, and it seems a signal emerges when primes are the input, it's just pure number theory and inverse fft

[regal summit]

Fair enough, though at some point you'll have to validate that paper

[graceful inlet]

I see.

[regal summit]

Anyways @placid stratus, sorry for the nastiness earlier, it's just that we get a lot of people acting like they've solved a major problem when they haven't come close

And I thought that's what was happening for a moment

[placid stratus]

I did do that kinda in the cs channel earlier so it's all good, turns out my algo was pseudopolynomial and doesn't solve P=NP :d

I appreciate the apology, people are often nasty to me when I'm just trying to share what I'm working on

[regal summit]

Well just make sure not to make any fantastical claims

[placid stratus]

The thing is, without a bit of hubris and fantasy, you can't tackle hard problems

[regal summit]

But your analysis of elliptic curves and primality is actually a valid approach

[regal summit]

Well yeah, but claiming to solve an open problem alone is too much hubris

[placid stratus]

I think it has to start that way, much of the time, someone tries something and gets an interesting initial result and they intuit a research direction and network a bit and the ball gets rolling

That process never starts if you don't believe you can get it going alone

So like, yeah, I genuinely believe I can solve any open problem, because having that belief has demonstrably and repeatedly led to interesting results

Sorry if it comes off poorly, it's just optimal

[regal summit]

Well, from my experiences so far, it's better to have that confidence with a team

Its pretty unheard of nowadays for someone to have discovered a major result without significant amounts of collaboration

[placid stratus]

Wiles, ABC guy

[long lion]

the last time someone shared a random graph here without any context, they claimed they had almost solved the riemann hypothesis by establishing a connection with DNA

[regal summit]

Wiles collaborated

[placid stratus]

That's not what everyone who developed prior art said

[long lion]

they also did not want to share any more than their random graph cus they were worried that someone would steal their £1m worth of work lmao

anyway yeah we get plenty of cranks here lol

[placid stratus]

I think there's a numberphile interview where some folks were salty because Wiles went off to a cottage for a year to yolo everything solo

[regal summit]

His initial ventures were done generally alone, but the finishing of his proof was done with Richard Taylor

Also it took him 7 years to solve the last theorem alone

[placid stratus]

I prefer collaboration I just want to prove a little piece here or here so my name can be on it then I can share everything completely and anyone who finds it interesting can have a field day

At the moment I guess I have a conjecture.. you can inverse fft the primes to generate smooth ovoids for unclear reasons

And symmetries also emerge, for no reason, if you include composites

So mister usually-working-on-parsing-algos college dropout here is gonna take a shot at trying to prove some component, write a little paper, and share it here in the coming soon-ish period of time

[livid finch]

hahah

applied mathematicians

[livid finch]

Also wiles already had a cushy position and tenure that allowed him to spend so long on the problem iirc

[placid stratus]

I'm even worse, college dropout programmer :d

Ideas find their ways into the most unsuspecting minds, sometimes

[regal summit]

I think this is what elliptic curve primality testing is

https://en.m.wikipedia.org/wiki/Elliptic_curve_primality

[placid stratus]

All this looks really complicated

Maybe I found a simple method of ECP

[regal summit]

I mean all of it is just common terminology in algebraic number theory

Along with some runtime complexity stuff

[livid finch]

At princeton too (basically the best math department in the world). I think — he was already an established mathematician

Like he proved coates-wiles

And that’s all I know about him tbh

[regal summit]

Yes he was

And even then it still took him 7 years to solve the last theorem

[livid finch]

coates wiles was pretty significant too

[placid stratus]

I'm gonna see what I can come up with in a weekend lol

[livid finch]

Good luck!

[placid stratus]

Then I'll write a shitty amateur paper and post it and maybe some real math folks might find it interesting

[regal summit]

And he also still collaborated with some coworkers towards the end

[livid finch]

For FLT? Yeah

He finished the proof with Taylor cus there was a big hole

[regal summit]

Yes

All of this is to say that not collaborating to solve major problems is not really a thing anymore

[livid finch]

Yes

[regal summit]

And those who possibly could are the best at their highly prestigious universities

[placid stratus]

Well, ABC guy tho?

[regal summit]

Who is ABC guy

[placid stratus]

Japanese name, can't ever remember it

[livid finch]

Mochizuki

[placid stratus]

Yeah, he still getting it validated?

Last I checked there's like 10 people who understand the proof

[livid finch]

I think he’s just like ignoring everyone

Cus scholze said it was wrong

I think it was scholze and someone else

Stix

https://ncatlab.org/nlab/files/why_abc_is_still_a_conjecture.pdf

Anyway scholze and stix said it’s wrong, mochizuki basically thinks they don’t understand him and kirti joshi is trying to help but idk doesn’t seem like mochizuki likes him either

I don’t know even a fraction of enough to say who is right or wrong

Scholze did win a fields medal and mochizuki is also not really a crank - he has a reputable background

[regal summit]

"You don't understand me" is not a valid argument in math proofs tho

[livid finch]

In fairness iutt is like so vast

Idk

I agree with you though

[regal summit]

I'm not much of a number theorist, so maybe it's just different here

[livid finch]

I do wish abc was solved though 😞

[regal summit]

Though frankly I could use more nt in my life

We'll see

[livid finch]

What field are you

[regal summit]

Still kinda figuring it out, but probably algebra

[livid finch]

Pure algebra 😮

Are you a junior ?

[placid stratus]

While I have you two here, can I share a more complete idea?

[regal summit]

Freshman but I've done a good amount of studying

I'm starting graduate coursework next semester so I can get a better understanding of what I really like

[livid finch]

Nice

[regal summit]

Sure

[livid finch]

Sure but im kind of a noob

High school senior

[regal summit]

Not sure i can validate number theory stuff

[livid finch]

I’m just observing

[placid stratus]

Well, you might find it interesting anyways

[regal summit]

Oh btw i meant college freshman

[livid finch]

I know

You have undergrad role

[regal summit]

Alright good

[placid stratus]

Eh, maybe I should actually write a paper

[livid finch]

It may be a good idea - more people can validate

[placid stratus]

I hate writing papers

[regal summit]

You can, but still, it has to go through significant amounts of peer review

[placid stratus]

I know but like, I don't care about that, I have nothing to gain as I'm not involved in academia

I just want to share the ideas so they lead to good stuff

But it's not very presentable as discord messages

[livid finch]

I think a paper is the best way to get your idea shared

[placid stratus]

How did people have the patience for this before AI?

It all makes sense in my head already and getting it communicable is actually awful

[livid finch]

I would not recommend using AI for writing any of your paper

Even if your ideas are correct, AI writing is very easy to spot and will make people immediately dismiss you as a crank

[placid stratus]

The code that generated the images was prompted

I just write prose when I get ideas and graph results and see what I get

I'll use it for generating graphs mostly, but its prose is not bad /shrug I still think I write better

Kinda weird how split the AI takes are in academia

Terence Tao is very into it

Anyways, will return when have something interesting to share, thanks for chat, was pleasant

[livid finch]

Terence Tao is into it for like very specific use cases

Like proof assistants I think

He did a talk at the IMO about it I think

[past spire]

What modulos do we have to check, to have for over 99,99% of numbers from 1 to n, when n goes to infinity a test if they are prime or not?

[still flare]

The primes

Then you even get 100% :)

[past spire]

But if I had a limit that I can only check 1000 modulos?

For one number

But probably checking primes is the best option

Never mind

The question doesn't matter

[graceful inlet]

Since it suffices to check up to sqrt(n), and sqrt(n)/n = o(1) as n → ∞, 0% asymptotically.

[sacred junco]

can someone help simplfy this expression? assuming z=x+iy

[torn escarp]

what have you tried so far?

[sacred junco]

so i came to this conclusion but i'm not sure of this solution

basically i replaced the -ve power by getting the conjugate of z

[forest plank]

You had correct idea. You just made a algebra mistake. 😊 Just verify for a 2nd time what you wrote. 😊

There are other fun ways to solve this too. For example $z^2 + \overline{z}^2 = 2 Re(z^2) = 2 x^2 - 2 y^2$ or $z^2 + \overline{z}^2 = (z + \overline{z})^2 - 2z\overline{z} = 4x^2 - 2 |z|^2 = 2x^2 - 2y^2$ 😊

[sterile pumice]

🤗🤗🤗🤗

[sacred junco]

Oh yess okay

i was just making sure i had the right idea

thank you so muchh @forest plank

[plain orchid]

,tex \begin{Theorem}
If (a\in \mathbb{Z}_{>0}), prove that (a\gcd(b,c) = \gcd(ab,ac).)
\end{Theorem}
\begin{proof}
Let (d \coloneqq \gcd(b,c)) and (e \coloneqq \gcd(ab,ac)). First,
we'll show that (ad \mid e). For this, notice that (d \mid b) and (d \mid c)
so (ad \mid ab) and (ad \mid ac). So, (ad) is a common divisor of (ab) and (ac) which tells us
that (ad \mid \gcd(ab,ac)).

Next, we'll show that (e \mid a\cdot \gcd(b,c)).

Since, (e \mid ab) and (e \mid ac), there are integers (s) and (t) such that (es = ab) and
(et = ac). Furthermore, there are integers (u) and (v) which are relatively prime such that (du = b) and (dv = c). So,
(es = (ad)u) and (et = (ad)v). So, (e \mid (ad)u) and (e \mid (ad)v).
Since, (u) and (v) are relatively prime, we can conclude that (e \mid ad) which completes the proof.
\end{proof}

[sterile pumice]

atomics

atomics

[plain orchid]

does this look right

[sterile pumice]

atomics

[last pier]

The argument definitely works if this statement is proven.

[last pier]

yes

[midnight shell]

im not sure if this is the right place to put this but there's this honors number theory course offered at my university and it says its designed to be a theoretical course designed for math majors. im gonna send the description and i was just wondering it its a reasonable class for me to take with no prior number theory experience. ive taken a course in algebra but just not nt

"Topics will be chosen from finite fields, proof of quadratic reciprocity, Chevalley-Warning theorem on solutions to equations over finite fields, p-adic numbers, Hensel's lemma, Gaussian integers and quadratic fields, the theorem on sums of two squares and four squares, Hilbert symbol, quadratic forms over p-adic fields, Gauss's theorem on sum of three squares, Dirichlet L-functions and Dirichlet's theorem on primes in arithmetic progressions, modular forms, the transcendence of e, theta functions."

im willing to do some independent study to prepare but only to a reasonable extent (a week or two as a side project would be ideal)

[long lion]

so when you say u haven't taken a course in NT, how much NT do you know?

like do the words "euclidean algorithm", "quadratic residue", "fermat's little theorem" etc. mean anything to you?

also probably better to post this in somewhere like #advanced-lounge

[livid finch]

Some analysis may also be useful too, especially for L-functions and modular forms

[midnight shell]

only the very little ive learned for algebra

[midnight shell]

mhm

[midnight shell]

yeah ive taken analysis too

[long lion]

i mean generally i find elementary number theory isn't that deep

if you've taken courses in say groups & rings normally that covers most of it

cus then you'll know about the euclidean algorithm, FLT which really is just a special case of lagrange's theorem etc.

i mean like heck you even do chinese remainder theorem for rings too

i think it would be good to have a brief look through some elementary NT, that might help with some motivation & wouldn't take too long

anyway yeah try posting this to #advanced-lounge, i really don't know too much advanced algebraic NT

[livid finch]

I echo everything that LY has said. Also, it might be helpful to look at the preface of the text your course is using (if they use one) as that often contains more details on prerequisites. good luck and have fun with the course!

Looks like you’re using Serre to be honest

I’ve found what I’ve read of it to be quite terse, so if you do use it I reccomend you supplement it with something else

[midnight shell]

okok thank u both!!! thats rlly helpful

i think ill brush up on some basic concepts over the summer then

theres not a whole lot of info about this course out there cause its a new class running for the first time this fall

but i might email the professor

[livid finch]

Good idea - the syllabus matches Serre’s “A course in Arithmetic” so I reckon if you use a text, it’ll be that one.

[leaden elk]

I dont understand this argument when they say 5 = (-lambda_2/lambda_3)^3 (mod 25) can we just divide both sides by lambda3 how does that work

[rugged locust]

it's because a number mod 25 has a reciprocal iff it is not divisible by 5

more generally a number mod n has a reciprocal iff it is coprime to n

and we've dealt with the case where lambda_3 is divisible by 5 already

[leaden elk]

so a number is coprime with 25 iff it is coprime with 5, is that correct ?

[rugged locust]

yes

[leaden elk]

alright makes sense thank you 🙂

I feel my mind expanding

[rugged locust]

this is an important point to make

think about why that's true, if you weren't aware of this fact previously

[leaden elk]

im aware 🧠

[regal summit]

Bezouts identity 🔥

[past shard]

Hey! I struggled solving this question, does anyone have an idea how to solve it?

[idle locust]

quick question, is there a way of simplifying a condition of the form "if x = c mod n or if x = -c mod n"? e.g. "if x = 1 mod 6 or if x = 5 mod 6"

[rugged locust]

x = +-1 mod n... lol

[regal summit]

plus or minus sign

$x \equiv \pm c \mod n$

[sterile pumice]

hiidostuff

[idle locust]

well, im looking for a format i could use in a computer program

[graceful inlet]

In general that's still probably the best in general.

Let's say n is prime; then this is equivalent to x^2 = c^2 (mod n). But do you want to have to compute a square every time you check the condition? It's probably more efficient to test x against each of c, -c individually.

You could define a function eq_pm(a, b) returning (a == b || a == -b) (do mark it inline if you can) and call that every time instead of writing out the condition.

[zealous shoal]

Checkout.. Poorly worded not my creation

[hoary shell]

Let p > 5 be a prime. I want to show that there always exists consecutive QRs and NRs

I showed for p>5 we should have at least 2,5,10 be a QR. We also know 1 and 4 are always quadratic residues

Ig it's already over lol. Then we would have a couple of tuples (1,2),(4,5),(9,10) as quadratic residues

How about quadratic nonresidues tho?

[west glade]

the only way for there to not be consecutive nonresidues is if it always switches between residue and nonresidue

[hoary shell]

Yeah right

I just want to write it explicitly. It's not as clear as the QR case

So ig I'm trying to show the existence of n,n+1 that are both NR

[west glade]

you only have p-1 slots, half of them QR and half NR. you know QR are consecutive somewhere

[hoary shell]

Are you implying if we have 2 consecutive QRs then we should have 2 consecutive NRs somewhere?

[patent acorn]

if you also take into account that 1 is a QR (because otherwise there would be counterexamples like N Q Q N)

then you scan through the string and break it into chunks of either Q N, Q, or N, prioritising Q N wherever possible

and there must be at least one Q chunk (arising from the pair of consecutive QR), so there's at least one N chunk, because the number of Q and N are the same

and because that failed to be a Q N chunk, and didn't occur at the start because the start is Q, that means there's another N before it

and that's your pair of two consecutive nonresidues

ok wait so simpler way to phrase it:
count how many QRs have a NR directly after them, this is strictly less than the total number of QRs
but that number is the same as the number of NRs with a QR directly before them, which is therefore strictly less than the number of NRs
so there's a NR with no QR directly before it, and it can't be at the start, so it has a NR directly before it

[hoary shell]

This is confusing

I know 1 and 4 are QRs so if I show 2 and 3 are consecutive NRs then I'm basically done?

[patent acorn]

well showing that would work, the issue is it's not always true, for instance 2 is a QR mod 7 (it's 3^2)

[hoary shell]

yeah that's the problem ig

how about we go by contradiction?
Assume we don't have consecutive QRs and NRs then we are looking at numbers modulo p in the following sense. Since 1 is always QR. We have {QR,NR,QR,NR,...}

now we know 4 is always a quadratic residue but we showed it's NR

Contradiction?

Idk sounds too good to be true

I'm more interested about the density of k-consecutive quadratic residues honestly but i need to get this down first

[patent acorn]

well that works, but it doesn't prove the result you wanted

all that shows is that there is either a consecutive QR or a consecutive NR

but we already knew there's a consecutive QR, by the "at least one of 2, 5, 10" argument

[hoary shell]

Oh...

Yeah I'm lost then LOL

[hoary shell]

I was trying to get my hands dirty on pigeonhole but I don't see it really

[forest plank]

Hmm there are 2 cases. Either -1 a qr or nr.

If nr then easy. We know that there are 2 consecutive qrs, let's say x,y. Then -y,-x will be consecutive nonresidues. Done.

If -1 is a qr. For contradiction, assume there aren't any consecutive nrs. Then every nr has to be followed by a qr. Between 1 and -1, we have to fill p-3 slots with (p-1)/2 nrs and (p-1)/2-2 qrs.

For each of the nrs, we need a qr to follow it. But we have 2 qrs less than nrs. Ok, one may be followed by -1. But then still we have a deficit of 1 qr. Contradiction.

[forest plank]

Lol. I just googled. You can count the number of consecutive qrs using the sum: $\frac{1}{4}\sum \left( 1 + \chi(t) \right) \left(1 + \chi(t+1) \right)$

By some manipulations this reduces to a quite nice formula

[sterile pumice]

🤗🤗🤗🤗

[forest plank]

(t ranges from 1 to p-2)

Soo, this is all equal to...

$\frac{p-2-\chi(-1)-1}{4} + \frac{1}{4} \sum \chi(t(t+1))$

[sterile pumice]

🤗🤗🤗🤗

[forest plank]

Hmm the last sum seems to be equal to -1, so in the end we get

$\frac{p-4-\chi(-1)}{4} = \frac{p-\chi(-1)}{4} - 1$ pairs of consecutive residues 🤔🤔

[sterile pumice]

🤗🤗🤗🤗

[forest plank]

Hmm and to count consecutive nonresidues we just flip the sign before the characters in the very first sum.. and after the manipulations, get

$\frac{p-2+\chi(-1)}{4}$

[sterile pumice]

🤗🤗🤗🤗

[robust prawn]

Is there any known conjecture that effectively states that "11 is the largest number that cannot be expressed as a sum of two or more distinct primes"?

I couldn't find anything on this

http://dx.doi.org/10.17654/JPANTAFeb2015_001_015

This paper claims that every integer greater than 11 can be partitioned into two or more distinct primes but the document isn't there

I guess I can email the author about their 10 year old paper lol

Oh wrong link

But this one has a download directly

No

Two or more

[patent acorn]

two or more distinct primes

[robust prawn]

Its all good

[sweet mist]

any hints for part b here? Supposed to be doable by hand I get 263*773 for part a, and my first thought was break it up into two congruences via crt etc and then use eulers theorem and write x^262=1 and hopefully 134843 is close to a multiple of 262, similar for the other inequality and I could breadk it up that way, but it doesn't seem to be.

[ripe peak]

Hey guys i have a question.
prove that the product of 4 consecutive integers +1 is equal to some square number

i just want to know the best way to approach this problem

[robust prawn]

There's most probably a more elegant method but:
$x(x+1)(x+2)(x+3)+1=y^2 \
x(x+1)(x+2)(x+3)=y^2-1=(y-1)(y+1)$
$y$ here must be odd, as $x(x+1)(x+2)(x+3)$ is a multiple of 4. As such, without loss of generality we can take $x$ to be even and see that since $y-1 < y+1$, we can try to assert that
A: $x(x+3) = y-1$
B: $(x+1)(x+2) = y+1$

A: $y = x^2 + 3x + 1$
B: $y = x^2 + 3x + 1$

As y is an integer, its square must be an integer (and thus exist as an integer solution to our original equation $x(x+1)(x+2)(x+3)+1=y^2$)

[sterile pumice]

7aman

[robust prawn]

If youre good enough at factoring (which I'm not) you could skip all of this and just show that x(x+1)(x+2)(x+3) + 1 = (x^2+3x+1)^2

Sorry for the formatting, by the way

[ripe peak]

i actually found another way for it.
after writing a few terms we can see that
$x(x+1)(x+2)(x+3)+1=(x(x+3)+1)^2$

[sterile pumice]

Aydin_RQ

[ripe peak]

but thanks for this i learned new techniques from it! ❤️

[ripe peak]

$x(x+1)(x+2)(x+3)=x(x+3)(x+2)=x(x+3)=[x(x+3)][x(x+3)+2]$

[sterile pumice]

Aydin_RQ

[placid stratus]

I'm back, and I've got some interesting results! I have a new algorithm that deterministically estimates primes.

What is interesting here is that generating more primes -> generate a curve that can generate more primes, so a sieve is possible, but that would require figuring out how to go from an approximate prime to the actual prime

I guess from here it will be possible to determine a tight candidate range and Millner-Rabin the items, and sieve only what is left; if only one item passes the Miller-Rabin tests, then it must be prime, and no sieving is necessary

Since Millner-Rabin produces no false negatives and has a 1% false positive rate, this massively reduces the computations necessary to sieve primes

It would be nice to eliminate sieving altogether and there is some potential to do that if there are patterns in the ifft of the exponents of "prime composites"

[placid stratus]

Oh wow AKS is a thing, that makes things easier

[analog ivy]

Idk where to put this but are these proofs decent?

[sacred junco]

Given a real number x that satisfies: x^3 + 6x^ 2 and x+(1/x) are integers. Prove that x is an integer.

pls help

[rugged locust]

That doesn’t sound right, if x is an integer then x + 1/x being an integer actually forces x to be +-1

[sacred junco]

wdym it doesn't sound right

wouldn't it still satisfied x being a real num in the first place

[torn kindle]

I've done some searching and need a bit of help. I've been trying to find a way to know the largest string of consecutive divisors of a number. I've been thinking about simplifying the divisors down to given numbers with only complete chains of prime divisors (which implies the number is even as well). From this I can use greatest prime factor as a starting point for a sieve to find the lowest number that does not divide a given number (aka. the number after the last consecutive divisor , call it m). My first step for the sieve was using the fact that m is either the gpf or a prime of power 2 or greater, and some primes squared will be larger than the gpf. Those primes can be exempt from being a possible value of m.

[sweet mist]

Yeah all looks good to me, so long as those are all laws/rules you have access to from class.

[sweet mist]

Just found a solution to this, can solve the CRT equivalences by raising both sides to the inverse modulo phi(p) of the power

[placid stratus]

Just debugged and it correctly generates the first 1000 primes! And I'm about to optimize the estimator so the space complexity is O(1). Nobody is curious?

[placid stratus]

generates the first million primes in linear-ish time

[livid finch]

what is linear-ish

primesieve does in O(n log log n)

[placid stratus]

fit a log^n curve, the fit is perfect as n->inf but n=4 sufficed for 500,000 primes for example (so n increases as the order of magnitude of the number of primes you want to generate increases), increment a linear time iterator until it matches the curve at each whole number index, the nth value associated with the index is deterministically ~prime and the window should be tightly bound by cramer's. from there miller-rabin can eliminate 99% of non-primes and AKS (or your preferred deterministic primality test) can confirm what's left

no sieving and no factorizing and no dependency on previous primes to determine the nth prime

using some novel math techniques based on k-smooth numbers to accomplish this

requires extending the definition of a function to include rewrite rules like in automata theory

i did not expect it to work this well

if anyone knows anyone interested in coauthoring a paper with me, let me know

[tacit pier]

Here, it says if "n does not belong to T", then it will "have a factor that does not belong to T". Now using the example, if we have one factor from T, say 40, another that does not belong to T, say 4, then we have 160 and it still belongs to T

It says any factorization of "n does not belong to T" must include a factor that does not belong to T

But I see it must have all factors that does not belong to T. If there's even one factor from T, then the whole number n belongs to T

I feel confused

[charred roost]

Your observation is correct, but it doesn't contradict what is written in the image. The integers with remainder 1 mod m are closed under multiplication, but the integers with remainder 0 mod m have a strictly stronger property, they are closed under multiplication by any integer. (This is sometimes called super absorption, and you''ll see it when you learn about ideals of rings in abstract algebra)

[tacit pier]

Thanks for the answer. I don't fully understand it but hope to understand in the future

[merry moth]

can anyone help me?

[upbeat shuttle]

Consider what happens when $a+b=0$ and think about transcedental numbers

[sterile pumice]

person52434509

[merry moth]

Oh thx

[livid finch]

Out of curiosity did you find out?

[latent gate]

Random but I saw this message and was briefly seriously confused as to why I did not remember sending it

[midnight shell]

i would be able to take it and understand with a brief study of some elementary nt stuff

but its at the same time as a class i really need to take :( so i wont be able to

[livid finch]

noo what a shame

hopefully you get another chance!

[midnight shell]

yeahh i hope so too

it seems super interesting

i have to take a nt class to graduate anyway but im hoping i can do this instead of elementary nt

[edgy vessel]

Let $p$ be an odd prime number, and $x$ be an integer such that $p \mid x^3 - 1$ and $p \nmid x - 1$. Thus $p \mid x^2 + x + 1$.

Let $S = x - \frac{x^2}{2} + \frac{x^3}{3} - \ldots - \frac{x^{p-1}}{p-1}$. I want to show that $p \mid S$.

If we clear the denominator, we get $(p - 1)!S \equiv x((p - 1)! - \frac{(p - 1)!}{4} + \frac{(p - 1)!}{7} - \ldots) + x^2(\frac{(p-1)!}{5} - \frac{(p-1)!}{2} + \frac{(p-1)!}{11} - \ldots) + \frac{(p-1)!}{3} - \frac{(p-1)!}{6} + \frac{(p-1)!}{9} + \ldots$. I am wondering how should I finish it? This is a polynomial similar to $x^2 + x + 1$ just with additional coefficients

[sterile pumice]

Luke

[long lion]

you can say a bit more about p since p | x^3 - 1 but p !| x - 1

also i think it'd be easier to work with fractions rather than clearing denominators, there's no particular reason why clearing denominators would make it nicer

[midnight pecan]

How come when you're finding the exponent for a prime $p_i$ in the prime factorization of $n!$, you take the sum of $\left\lfloor \frac{n}{p_i^k} \right\rfloor $ over $k$ rather than $\left\lfloor \frac{n!}{p_i^k} \right\rfloor $?

[sterile pumice]

phoenixperson

[midnight pecan]

the dividing by $p_i^k$ and summing over k makes complete sense to me. It's just the numerator that slightly confuses me

[sterile pumice]

phoenixperson

[last pier]

what is the context for this

[midnight pecan]

message right above that one

finding prime factorization of n!

Basically, you'd first take the floor of either n/p_i or n!/p_i because you'd want the number of factors that divide n! (that's why I think it should be n! but the official solution says the numerator is n), and take the floor of that so as to not overestimate. Then, you want to count one of floor(n/p_i^2) or floor(n!/p_i^2) because if it has a multiple of p_i^2, then it should be counted twice into the exponent's factorisation. floor(n/p_i) covers the first instance of this count.

https://unacademy.com/content/ssc/study-material/mathematics/power-of-a-prime-number-p-in-n/#:~:text=The general equation to find,and this contributes one p. has the solution and it says you sum up floor(n/p_i^k)

[midnight pecan]

Oh I get why it's just n now

floor(n/p_i^k) represents in how many instances in n(n-1)(n-2)(n-3).....3*2*1 does p_i^k appear

[idle locust]

n and m are coprime. if (a * n^-1) mod m < (b * n^-1) mod m, is that equivalent to a mod nm < b mod nm ?

[idle locust]

or just any other equivalence of a similar form

i feel like there must be one

[loud maple]

What is the ordering here?

[idle locust]

treat "mod m" as a function being applied to the terms in the brackets

so "(a * n^-1) mod m" is an integer from 0 to m-1, which is compared to other integers under the usual ordering

im looking for a statement equivalent to (a * n^-1) mod m < (b * n^-1) mod m that retains the relation while not having an inverse term, basically

[storm mist]

i don't understand how sum formula works in solution of chinese remainder theorem. it is known, that for i != j term of sum is eliminated (we can extract m_i from r_jM_jM(^-1)_j). do we sequentially solve formula for each m_i? (i mean, we have fixed m_1, and then solve every term of sum for this fixed module, and so goes on for every i?)

i am confused about notion of sum in CRT, how do we interpret this? seems like we work with (the same) linear combination per each x in system, and the solution of system is a bunch of remainders (r_i), which are related to each term in lin.combination modulo each m_i? still can't explain how do we come to sum..

[edgy vessel]

prove that $n^6 + 6^n$ is composite when $n$ is an odd multiple of $7$

[sterile pumice]

Luke

[lament gyro]

Do you know fermats little theorem?

Or eulers theorem ig. Helps a fair bit

[edgy vessel]

Yes but I wasn’t sure how to apply it here

[lament gyro]

What's the totient of 7?

And what does that imply about n^6 mod 7?

[lament gyro]

Oh my days. There's actually a really slick proof of this.

Just note that -1 (mod 7) = 6 🙂

[lament gyro]

Actually they've given you stronger assumptions than you actually need.

[regal summit]

They give the base necessary assumption

n^6 ≡ 1 mod 7 when n = 7

6^n ≡ -1 mod 7 when n = 2k+1

[cedar stag]

._.

[edgy vessel]

What’s the proof though

[cedar stag]

that the set of all natural numbers is the same size as the set of all square numbers is a bit counterintuitive

the square numbers get more spaced out, so how..

[cedar stag]

is it only because both sets go to infinity?

[lament gyro]

7^6 (mod 7) = 0 btw. Also, n^6 = 1 mod 7 holds for all n != 7m for m in Z

[lament gyro]

What have you gotten so far?

I'm happy to give more hints you just need to tell me what you are stuck with.

[regal summit]

Oh oops LOL

I screwed up

[tough edge]

Take the set of natural numbers. Now square every number in the set. Voila, you now have a set of all the square numbers!

(being careful to check that no two natural numbers might square to the same number)

[cedar stag]

wtf

[tough edge]

real

[loud maple]

Two sets are said to 'have the same size' if and only if there exists a bijection between them

It is easy to verify that the function $x \mapsto x^2$ is a bijection from the set of natural numbers to the set of squares of natural numbers

[sterile pumice]

KnightWatch

[edgy vessel]

Its $6^n$ not $n^6$

[sterile pumice]

Luke

[edgy vessel]

Can you write your proof, I think you may be mis-understanding the question, it is not a trivial application of fermats little theorem

[lament gyro]

I'll just outline it for ya.

[lament gyro]

but I've got an assignment due in like 2 hrs so I'll just be brief and I wont hve time to answer any q's. Sorry, but I gotta lock in for this thing.

so observe that n^6 (mod 7) = 0

[edgy vessel]

But n is a multiple of 7...

[lament gyro]

my bad. typo

so then 6^n mod 7 = 6

so n^6 + 6^n = 6 mod 7

then consider mod 9

n^6 = 1 or 0 mod 9

youll have to consider 2 cases

then obviously 6^n = 0 mod 9

for n > 1 anyways.

n = 1 is trivial

but then you have 6^n + n^6 = 0 or 1 mod 9. if its 0 youre done

otherwise I woul compare with the 7 and use CRT to simultaneously solve the two and hopefully find a gcd != 1

you may need to consider a different factor aswell. the 7 was just for example, I have a feeling that 5 works tho

a bit tricky to find n^6 tho

but still doable, you just have to find inverses.

[lament gyro]

the clean proof that I was refering to before basically just uses this fact

then apply Fermat test

And even if you dont know fermat's test it follows directly after fermats little theorem

so if you understand FLT, I trust that you can reason about fermat's test

and its basically juts a 6 line prof to solve your question

sooper slick

but you do have to play around with some stuff to make it work

[edgy vessel]

The question is also equivalent to showing $\gcd((7^6 + 6^7)(k^6 + 6^{7k}), 7^6 \cdot 6^{7k} + 6^7 \cdot k^6) > 1$ which seems like induction, but it also feels like too many symbols

[sterile pumice]

Luke

[edgy vessel]

I can't figure it out, do you mind sharing whenever you get the chance

[velvet mantle]

can someone help me with this question

[foggy granite]

hello! i need to use the infinite descent method to get 1973 as a sum of two squares, but i'm not sure what the next step is. I've attached the original problem + my work.

[foggy granite]

an update to the work, got stuck again.

[forest plank]

Maybe here mistake? In one bracker should be plus, in other minus. Here you have both pluses

[foggy granite]

Oh shoot, maybe.

I must've put it right into the calculator because i get the same result.

i'm just curious if i'm supposed to have gotten that negative value at the end of what i sent.

realized another mistake i made, but not sure how i got the negative still.

[analog ivy]

Proof good or proof bad

[rugged locust]

the proof looks fine, but alternatively, you can show that the product of two numbers of the form p+xsqrt(q) must also be of the form p+xsqrt(q)

[foggy granite]

Oops, I changed it. Am I supposed to get the negative value?

[forest plank]

Well it doesn't matter really if it's negative. Because it's under square

[livid finch]

Unrelated but really nice handwriting, what pen do you use?

[analog ivy]

Uniball one 0.5 black

[slate juniper]

I'm pretty sure I've posted this here before

but

https://tenor.com/view/wth-steven-he-what-the-hell-gif-26581944

76^n is congruent to 76 (mod 100) for all n \in Z?

wait I think I remember

let me see

[still flare]

You can easily guarantee the existence of nontrivial idempotents modulo any composite

This is an immediate consequence of the chinese remainder theorem

Note 76 is 0 mod 4 and 1 mod 25.

[quaint gate]

<@&268886789983436800>

[unkempt void]

You made me realise smth lol

1 presumably doesn't count as a composite number so it is neither composite nor prime lol

[still flare]

Well um it satisfies 1 | ab => 1 | a or 1 | b so 🤓

But yes, it's a unit

[slate juniper]

chinese remainder theorem...do I need to review the basic version before I study the ring theory version(in chapter 7/8 of D&F)?

[woven marten]

Hey, having the identity in the picture, little Fermat’s Theorem and the fact that:
If GCD(n,m)=1, then u = v mod mn iff u=v mod m and u=v mod n.
How can I prove Eulers Theorem? I mean a^phi(m) = 1 mod m.
Thanks a lot

So far I managed to prove:
For all k a^phi(m) = 1 mod p_k, but idk how to get the exponent into p_k

[rugged locust]

In the statement of the Chinese remainder theorem, the v isn’t necessarily the same v

The statement is that the system of equations {x = u mod n, x = v mod m} has a unique solution {y = w mod mm} iff gcd(m,n) = 1

You can find w with the division algorithm, but there is no easy way to express it in terms of u and v

[rugged locust]

Also, the Euler-Fermat theorem is only true when a is coprime to m
(for instance take m=4 and a=2)

Otherwise a^phi(m) = 1 mod m is not true

But I don’t immediately see a way to prove EF by using CRT

[woven marten]

Yes, I forgot to mention that.

[rugged locust]

I could give you the standard group theory proof for the theorem if you want (you don’t need to know group theory to understand the proof)

But it is a medium length proof without using some of the more advanced theorems

[woven marten]

Unfortunately Im asked to use those things I mentioned above to prove it, so group theory proof wouldnt be any good. Thanks tho

[rugged locust]

Actually now that I think about it the CRT is necessary to prove the isomorphism between Z/Znm and Z/nZ x Z/mZ. so this might be doable after all

But it is late for me so someone else will have to think about this

[still flare]

Nah

They're basically saying literally the same thing, but the ring theory version is just more precise

and concise

[woven marten]

I managed to do it using binomial expansion and multiplicativity of phi.

[surreal crescent]

there’s one by induction and some cases. I think it’s nice altogether that group theory proof is more elegant

[sweet mist]

Pretty new to finite fields, and its not covered in much depth in this course(more of just a sidenote since you work over this specific class of fields in AES), so not too familiar with working with them. I've found that the inverse of p(x) is x^7+x^5+x^4+x+1, but I'm at a loss for how to find p(x)^17 for part b)

Even computing small powers of either p or p^-1 as a test if maybe something will pop out seems overly tedious, this lecturer doesn't tend to make exercises tedious or require much guesswork

[sweet mist]

ping on response if anyone has any idea, but I might be asleep and not able to respond.

Oh wait

17 divides 255

something lagranges theorem

maybe....

Since GF(2^8)* is a group under multiplication with order 255, the orders of its subgroups are either 1, 3, 5, 17, or 255... Then what?

Seems like I'd also need to compute p^3, p^5, and p^255 to rule out that lagranges thm gives p^3=1 etc instead

[west glade]

p^255=1 anyway

so the question is whether p^k=1 before that

and the only options are p^1, p^3, p^5 and p^17

most of these arent that hard to compute

due to being close to a power of 2

but yeah it will take some time

[eager silo]

d = gcd(a, a*(.....something)) = a
c | b means that ac | ab means that ac | bd

[velvet mantle]

okay thank you

[sweet mist]

Oh right since 17 divides 255 of course thanks

I guess its time to get my computation gloves on

[sweet mist]

I'm losing my mind

[sweet mist]

done now.

[modest coral]

i'm looking for primes p such that n^4+1 is divisible by p^2 for some integer n
that would mean n^8 is congruent to 1 mod p^2, so the order of n is 8
so 8 divides phi(p^2)=p(p-1)
so the smallest candidate for p is 17
does that make sense?

but how can i find an n of order 8 mod 17^2?

[long lion]

here's one way you could go about it

(Z/17^2Z)x is cyclic of order 16*17

notice that 3 is a primitive root mod 17 and 3^16 != 1 mod 17^2

so (Z/17^2Z)x is generated by 3

then find the right power of 3 to find such an n

[modest coral]

then we need 3^k where 17*16 / gcd(17*16,k) = 8
so k = 17*2, 17*2*3, 17*2*5, or 17*2*7
we get 3^k = 110, 134, 155, or 179
thank you
i have a question, how do we know that (Z/17^2Z)x is generated by 3?

[long lion]

uhh theorems

basically we know ord_17^2(3) is divisible by 16

so you just need to show it's 17*16 and not 16

you check it's not 16 manually

and then it follows it must be 17*16

[modest coral]

oh right

[long lion]

actually with a bit more work, you can actually show 3 generates (Z/17^kZ)x for every k >= 1

(basically lifting the exponent)

(the theorem is if p>=3 is an odd prime, and a is a primitive root mod p, then as long as a^(p-1) != 1 mod p^2 then a generates (Z/p^kZ)x for all k >= 1)

(it's quite useful)

[modest coral]

where can i learn theorems like that?
would that be in a number theory textbook?

[long lion]

yeah just like some introductory number theory book

tbh i don't personally really know of any books, but like yeah u can ask around

or like ur uni's NT course would probably suffice too

[modest coral]

thanks

[shut flax]

does anyone know if there are infinitely many pairs (m,n) with n>m, such that n-m=d(n)-d(m), where d(n) is the number of divisors of n. Some examples are (1,2),(13,15),(25,28),(44,48),(59,63),(62,66),(106,112)

or can any integer k be expressed as d(n)-d(m)=k=n-m for some (m,n)

i havent seen anything related to this, but i didnt look very hard

[weary rune]

my uni NT course barely covered anything of substance

we stopped at an incomplete treatment of primitive roots

[thick panther]

if you just look for number theory then you will probably not get what you're looking for; you should search for elementary number theory

[barren elbow]

Could anyone share their opinion on which one of these looks easier to read?

[silver oak]

i can imagine there's a skill to reading left side, so someone would prefer left, because they know how to read it

which isn't even the same as easy

so yeah must be right

[fathom sierra]

I can read the right w/o zooming
the dark red on the left makes it essentially unreadable w/o zoom

@barren elbow

[barren elbow]

I see that now, thanks

[reef lark]

hi, I'm trying to get an upper bound on the number of integers $d = 3^g-x^2$ with $2\mid x$ and $0<x<\sqrt{2 \cdot 3^{g-1}}$ such that $p^2 \mid d$ for $p>3$ prime

[sterile pumice]

prakhar

prakhar

[barren elbow]

Is this a valid way?

[thick panther]

floor

[tough edge]

Why are you taking floor of just x anyway 😭 you should be imputing an integer

Inputting

[cunning spade]

looks like your trying to take the floor of x but im not sure

[smoky stream]

https://tenor.com/view/twistedtea-gif-19743210

[shut flax]

I wanted to keep things consistent

😦

[modest coral]

does $\gcd(a,b)=\gcd(a,kb)$ if $a,k$ coprime?

[sterile pumice]

Axe

[primal pewter]

yes

[modest coral]

thanks 🙏

[worn folio]

nvm that didn't include anything about gcd

[modest coral]

does $\gcd(a^2,b^2)=\gcd(a,b)^2$?

[sterile pumice]

Axe

[eternal cloud]

Try writing a in the form of d(a’), similarly for b where a’ and b’ are coprime

Then some calculations and using the fact that if a,b are coprime then a^2 and b^2 are still coprime

[modest coral]

gcd(d^2 a'^2, d^2 b'^2)

it seems true, doesn't it?

[eternal cloud]

Yeah

It also generalizes nicely to $\gcd(a^k,b^k)=\gcd(a,b)^k$ for $k \in \mathbb{N}$

[sterile pumice]

Catgod

[modest coral]

$\gcd(ab,ac)=a\gcd(b,c)$?

[sterile pumice]

Axe

[modest coral]

thanks 🙏

[abstract ferry]

me when number theory channel is being abandoned:

[unique cypress]

not anymore

[neon dew]

numba theere...

[neon dew]

seems like no one really does number theory 😔

weird considering there's a quarter of a million people here

[modest coral]

I'm working through modern olympiad number theory

When the problem is a proof it's harder to get feedback. For that reason I like problems where the answer is a number

my proofs sometimes don't match the approach suggested by the hints

[neon dew]

[regal summit]

plenty of people do

just no one really does elementary NT

[rugged locust]

Tbf elementary NT consists of like, 3 theorems, maybe 4 if you wanna push it

And I hate one of the 3 so really it’s 2

[long lion]

which one do you hate?

[long lion]

it's more that no one really does elementary number theory other than for olympiads/at the start of uni

[rugged locust]

Chinese reminder theorem

[long lion]

ic lol

[rugged locust]

I have no beef with the other 2 though, they’re great I like them a lot. You can probably guess what they are

[long lion]

FLT/Fermat-Euler and idk what the other one ur referring to is

the fact that F_p is a field?

[rugged locust]

I was thinking of Wilson’s, even though it gets vastly over shined by its bigger brother in terms of usefulness

[long lion]

ah ic

[modest coral]

(Z_n)* under multiplication is cyclic right?

wait that can't be right

[west glade]

its cyclic iff n=1,2,4,p^k, 2p^k for odd prime p

[modest coral]

oh cool

that's why it worked for 17^2 earlier

thanks 🙏

[wintry oriole]

Hello friends! Can anyone offer some tips on showing $\gcd(ab,n) = 1$ when $\gcd(a,n)=\gcd(b,n)=1$? I have two proofs but they rely on the existence of prime factorizations and I get the sense that is not what the textbook was intending.

[sterile pumice]

Tysty

[modest coral]

i think it follows from bezout's identity

we have aw+xn=1 and yb+zn=1 for some w,x,y,z
then (aw+xn)(yb+zn)=1 so (wy)ab+(awz+xyb+xzn)n=1

[rugged locust]

there's nothing wrong with using unique factorisation, it's a perfectly valid proof

[wintry oriole]

Thanks!

[regal summit]

I think they just wanted to know the alternate proof the book was expecting

[tulip vortex]

No quadratic reciprocity?

[rugged locust]

That’s the 4th one

But i personally consider QR to be an intermediate theorem, its not that elementary

[tulip vortex]

yeah all the good proofs are not elementary

rip fundamental theorem of arithmetic though

[surreal crescent]

why?

isnt this is a cool elementary nt problem

find all positive integers $n$ such that $\sum_{i=1}^{n} \frac{1}{i}$ is an integer

[sterile pumice]

hockeydude85

[regal summit]

pretty sure this is n=1 only

but no one does elementary NT because research-wise its dead

[surreal crescent]

yeah but why

[surreal crescent]

yeah

[regal summit]

idk ive just seen it somewhere

[surreal crescent]

yeah I think it is a kinda well-known problem

[regal summit]

pretty sure you have to show that the parity of the top and bottom are always different for greater cases