elementary-number-theory

[sage fern]

a little dense but kinda neat

[noble pumice]

Interesting

Will definitely read

I thought about it a bit you could have a complex base i think

[eager tendon]

Hi guys, I was wondering

How is that a corollary of Fermat 's little theorem?

[stiff rivet]

it isn't unless n is prime

the picture says its a corollary of euler's theorem

[eager tendon]

Oh yeah you are right, I just need that a is coprime with n

I found a proof, thanks for your feedback!

[woven lynx]

why with totient function is it for example with 12 3/4 * 2/3 * 12 and not 12 - 1/4 * 12 - 1/3 * 12

[thorny trail]

Hi there. I've got a number theory question. I'm trying to prove what's included in the photo above. I don't understand how if I raise "a" and "b" to some power, let alone the fact that the power is a prime number "p", I don't need "p^p" but only "p^2". I did some simple examples and couldn't find a pattern. I suspect it has to do with each number's prime factorization, but even if that was the case, I still don't know what I'm supposed to do. Confused all around and could use some help! Thank you kindly!

[lost falcon]

hi. i recommend returning to the definition of congruence mod p. how might the binomial theorem help you in this case?

[fading gulch]

Help I got a view matrix of

0 0 1 0
1 0 0 0
0 1 0 0
0 0 -1 0

How to make it do stuff?

[sacred junco]

wrong channel try #linear-algebra or dm me since I work with computer graphics.

also bad question.

[sacred junco]

Solve over the integers, 2^x-5^y=39.

[heavy mountain]

Could anyone tell me how to find all solutions for x here? I got this far and don't know what to do next

[sage fern]

,rotate

[unkempt void]

Seems you're more or less done honestly; 28x = 20 mod 28 iff 7x = 5 mod 12 iff x = 11 mod 12

So the general solution is simply x such that x = 11 mod 12 i.e. x = 12n + 11 for n an integer

[heavy mountain]

Okayy tysm ^^

[unkempt void]

np

[vivid stag]

So I have solved this proof and there's a question that follows it

This is the problem

I assumed to use the prime factorization of 15

which is 3 and 5

make them both in separate congruences

where I put

2^15 congruent to 1 (mod 2^3 -1)
and
2^15 congruent to 1 (mod 2^5-1)

so one is mod 7 and the other is mod 31

I get that this congruence is congruent to 1

i then divided 2^15 - 1 which is 32768 - 1= 32767

i divided by 7 and then 31

which left me with 151 which is prime

and that would be my prime factorization. Now my question is: Is this correct? And is this what was stated by using the theorem i just proved?

<@&286206848099549185>

[unkempt void]

yeah that seems good, although no need to talk about 'congruent to 1 mod 2^5 - 1' etc, you can just say that e.g. 7 = 2^3 - 1 | 2^15 - 1 (because 3|15) from the above problem

and similarly for 31

[vivid stag]

Oh alright, thank you very much

[unkempt void]

np

[vivid stag]

I was very iffy on my answer because it seemed like it should be a little different

[smoky sky]

Head over to https://discordservers.com/bump/268882317391429632 to bump this server!

[opaque spoke]

The Fun module is disabled in this server.

The Fun module is disabled in this server.

[sacred junco]

idk how i'll do tho ¯_(ツ)_/¯

[vernal current]

Can every sufficiently large integer be expressed as the sum of two squares?

I'm looking to prove or disprove

<@&286206848099549185>

[shell minnow]

this article might help you https://en.wikipedia.org/wiki/Sum_of_two_squares_theorem

[vernal current]

Yeah i saw that article. The links are broken though

I want to prove it

[sage fern]

no, as any square is of the form 4k or 4k+1, so the sum of two squares is of the form 4m, 4m+1 or 4m+2, so any integer of the form 4m+3 cannot be expressed as the sum of two squares

if you want a large integer, let m = 10^9, then 1000000003 is not a sum of two squares

[patent escarp]

Interesting problem that I think you should try: Prove weather or not (without using brute force) that there are two perfect square numbers that have a difference of 74.
Idk if this is common knowledge about what numbers can be the difference of squares but I’m still proud of figuring it out myself.

alsot ry to find a proof for n.

[rugged moth]

a²-b²=(a+b)(a-b) then factorize 74

[patent escarp]

Solution: ||There is none. Because 74 is even but 74/2 is odd, every way to factorize 74 into two numbers will have one even and one odd number. All difference of squares can be written as (a+b)(a-b), so for 74 to equal this, you need two integers that add to an even number and subtract to an odd number (or vice versa), which is impossible.||

[main comet]

👍🏼

[zenith dagger]

So I am having trouble with this counting: Let us fix a k-term arithmetic progression on {1,2,...,n}. I want to show it can intersect at most (n-1)k^2/(k-1) other AP in {1,2,3...,n}. So there are k choices to get which term is intersected, and then n-1 choices to get two terms of an AP which must intersect our given k -length AP. This counts all the two term AP that intersect our fixed AP, but I am unsure how to count the rest. The issue is that just with two points, I still have not defined what the starting point and difference in our AP is. I was wondering if there was good way to interpret the expression

[sage fern]

oh, i instinctively just looked at it mod 4

all differences between two squares are odd or a multiple of 4

[patent escarp]

yes

[main comet]

Ah nice!

[vernal current]

9-4 = ?

[sage fern]

odd

[vernal current]

Oh i see. Nvm i misinterpreted that

[tulip vessel]

he said odd or multiple of 4

so still satisfies

[quaint hare]

Bezout's Lemma is best girl

fight me nerds

[patent escarp]

I need help with something i’m making. I know it sounds really obscure, but I need to find a way to generate all positive integer values of a and b where a^2+b^2+6ab is a perfect square

[warm geode]

0^2 = 0 mod 4
1^2 = 1 mod 4
2^2 = 0 mod 4
3^2 = 1 mod 4

Consider the combinations

Knowing that a perfect square must be 0 or 1 mod 4

[livid birch]

how can i continue this

semi duplicate of what i asked in advanced but i had no idea this existed and it's probably more of an elementary thing anyways

trying to prove that p|a^p - a for all a

[wooden crater]

(x+y)^p = (x^p + y^p) mod p for all integers x and y by the binomial theorem

then induct on a

[livid birch]

this is new to me

[torpid charm]

finally (x+y)² can be x² + y²

[livid birch]

wait

we know x^p - x is divisible by p

so if we just add that

we get the inductive form

and know it's divisible by p

[sterile pumice]

hufflepuff
Compile Error! Click the reaction for more information.
(You may edit your message to recompile.)

[unkempt void]

a should have an inverse mod n i.e. (a,n) = 1

for example if n = ac, then if x = b + c (which is not b mod n), we could have ax = ab + ac = ab mod n

[unkempt void]

yh hcf or gcd

(a, n) is alternative notation sorry

[unkempt void]

But yeah it comes down to this (you can prove that they have an inverse if and only if gcd(a, n) = 1 by Bezout's lemma)

[sterile pumice]

hufflepuff

[unkempt void]

Hcf of what

well if you divide a and n by the hcf of a and n then the new hcf is 1

so yeah just comes down to what i said originally ig

Have you done bezout's lemma?

well i wouldn't write = for the statements being equivalent

but the idea behind it, sure

Well

Is h the hcf of a and n lol

[sterile pumice]

hufflepuff

[unkempt void]

Yes, the second is the same as the first ultimately because hcf(h, n) = h if h is a factor of n

It's nice to realise this is just saying a is invertible mod n iff hcf(a, n) = 1

(Those are the units)

(And yeah that leads very quickly to Fermat's little theorem)

Ye fair

Np

[sacred junco]

Hi !

If i have N a positive integer

I search a and b positive integer such as 2^a 3^b < N and it is the highest number of this form just before N

[livid birch]

any hints pls

🚨 not asking for soln 🚨 just a nudge

[sullen rune]

@livid birch for the examples you're writing, also look at the remainders

[livid birch]

it’s always 2

not sure what that means tho

[sullen rune]

investigate

[livid birch]

ok

[livid birch]

ig the hypothesis would then be that remainder is 2 for all n > 1

and pf by induction?

oh didnt know that sticker was a thing

[sleek cove]

whats the name of problems for smth like this $\frac{1}{x} +\frac{1}{y} + \frac{1}{z} = \frac{n}{m}$

[sterile pumice]

Sideurk

[sullen rune]

@livid birch it's simpler than induction, what does n^2+1 = k(n+1) + 2 mean?

[livid birch]

i tried messing around with that numerically but i kept running in circles

[sullen rune]

n^2+1 = k(n+1) + 2
n^2-1 = k(n+1)

know anything about n^2-1?

[livid birch]

k = n - 1

[sullen rune]

bam, that's the entire proof that the remainder is always 2

[livid birch]

ok a few things

1. how did you come up with the idea to look at the remainders? is that just intuition i might be lacking?

[sullen rune]

it's just that most number theory questions are about remainders/modular arithmetic

[livid birch]

i'll be sure to internalize that then lol

this isnt for a class, i just found sierpinski's book of problems in the library ¯_(ツ)_/¯

[sullen rune]

if you happen to think n^2-1 = (n+1)(n-1) when looking at the question you instantly see the answer too

[livid birch]

so you'll probably see me in here asking about more of those

[sullen rune]

cool cool

[livid birch]

another thing tho

[livid birch]

why lol

like i couldve gotten to that and thought "well shit what now"

[sullen rune]

yeah it's sort of going backwards in the proof, you start at what you want, n^2+1=k(n+1)+2, and keep changing it till you get an obvious statement

once you see k=n-1 you see k is an integer so it all works

[livid birch]

ohhhh

so getting a "definition" of k just means that it hold for all n

"it" being the form that we started with, which implies that the remainder will always be 2

that's so cool

man i wish my uni offered this class :(

(is that line of reasoning right)

at least it seems like number theory might be easier to self study than some other parts of math

or at least im more willing to just do problems in it lol

[inner anchor]

Egyptian fractions?

[sleek cove]

yes this is it thank u daddy

[inner anchor]

Np and blocked

[sleek cove]

[ionic pier]

what do $a', b', n'$ stand for?

[sterile pumice]

DVD_Koce_DVD

[ionic pier]

and what is the problem exactly

[pale turret]

Hi, I want to show that N has either a non-trivial common factor with (x+1) or (x-1) and somehow I can't find a good approach on how to do it best

[sleek cove]

what is upside down v

[pale turret]

is this related to my question? If so I just do not know what you mean :/

[sleek cove]

yes

there is an upside down v

[pale turret]

ah 😄

its a 1

[sleek cove]

oh..

well you can just apply the definition of mod

[pale turret]

sorry for my bad writing, next time i will use latex again

[sleek cove]

a=b mod n iff n| a-b

also ive never seen anyone write 1 with an up and a down

its usually just ~~ ∧ ~~1 line

[pale turret]

thanks, let me think about it for a minute. 🙂

[sleek cove]

have you seen that before

[pale turret]

yes

[sleek cove]

okay ye, use that

[pale turret]

unfortunately i still couldn't show the statement "I want to show that N has either a non-trivial common factor with (x+1) or (x-1) and somehow i can't find a good approach how to do that" using the tip. Can someone maybe help me again ?

[pale turret]

but what is if k>1

[sleek cove]

k isnt what you should be considering

[sacred junco]

Sorry, I think I posted my question on the wrong channel

Can I repost it here?

Z is a group made up of 213 peeps with A, B and C belonging to Z. 48 belong to A, 71 belong to B and 94 belong to C.
If two people from the same group meet, nothing will change.
If two people from two different groups meet, they will convince each other that they have made the wrong choice and join the third group.

How can I show that group Z will never unite using the congruence of relation modulo n?

Sorreh

[gilded bolt]

What will be remainder when 2(26)!+1 divided by 29

I try to use willson theorem

(28)! =-1 mod(29)

28 x 27 x (26)! =-1 mod (29)

How to proceed from here?

[sacred junco]

I found that the relation is mod 3, but how can I model the evolution of the situation mathematically??

HEllp your boy Ronald pleashe

[sacred junco]

Perhaps try a congruences table?

[cursive trail]

multiply by 26^-1 and 27^-1 mod 29

Since gcd(26, 29) = gcd(27, 29) = 1 it's well-defined

[cursive trail]

gcd(48, 71, 213) = ?

[ionic pier]

@gilded bolt you could try the folllowing (the congruences are mod 29):

[sterile pumice]

DVD_Koce_DVD

[ionic pier]

but as you've correctly pointed out from the Willson theorem

[sterile pumice]

DVD_Koce_DVD

[ionic pier]

so the whole congruence is a 0 mod 29

Yeah, now that I'm looking at your solution you are basically there, you have made the observation that 28 x 27 x (26)! =-1 mod (29), and now the only thing left is to substitute -1 for 28 and -2 for 27 (mod 29) and ... QED

So the remainder is 0

[sacred junco]

What do you mean?

Do you mean gcd(48, 213) = 3

?

[cursive trail]

no

[austere osprey]

calculation of primes by graphing

[mossy shadow]

$(3\cdot5\cdot7\cdot11\cdot13\cdot17\cdot19\cdot23\cdot29\cdot31\cdot37\cdot41)$

[sterile pumice]

deleted user

[mossy shadow]

Is there a way to get the number of digits of this product without the use of a calculator

[torn escarp]

yes

[mossy shadow]

how

[torn escarp]

pencil and paper

[mossy shadow]

hmm okay

what if it was that product raised to 6

or like 10

$(3\cdot5\cdot7\cdot11\cdot13\cdot17\cdot19\cdot23\cdot29\cdot31\cdot37\cdot41)^{10}$

[sterile pumice]

deleted user

[austere osprey]

an efficient formula that proves primes has not yet been created

prime factorization is slow but works

[mossy shadow]

how would prime factorization help with finding the number of digits of that?

[austere osprey]

this?

[mossy shadow]

yeah

$152125131763605^{10}$

[sterile pumice]

deleted user

[mossy shadow]

to find the number of digits in that without the use of a calculator

[austere osprey]

well brute force computation is slow for these large numbers, for example (3x5x7)^10 has about 30 distinct prime factors

[mossy shadow]

oh but again, how do we find the number of digits in the number through the use of the prime factors?

[austere osprey]

you can't unfortunately use prime factors to determine the number of digits

[mossy shadow]

ohh i thought you said that you could so i got confused

is there another way?

[austere osprey]

that i'm aware of, sorry lol

[torn escarp]

if you know log_10(x), this rounded down gives you the number of digits

if you have log_10(x) then log_10(x^n)=n*log_10(x) so you can just multiply by the exponent and then round your result down

that's about as best as I can see to do

[mossy shadow]

would you round it down everytime?

for a number like 33^6 for example, we get 1,291,467,969 which has 10 digits

but log(33^6) would be 9

if we round it down

[torn escarp]

oh and add 1 after you round down

try to derive the formula for yourself, it comes from looking at $10^n \le x < 10^{n+1}$ and taking log base 10 and thinking about how many digits they have

[sterile pumice]

Merosity

[mossy shadow]

ohh

great tysm

[inner anchor]

you are missing a -1 from $\left(\frac{227}{11}\right)$

[sterile pumice]

Pappa

[inner anchor]

the relation you have is

[\left(\frac{11}{227}\right)\left(\frac{227}{11}\right) = (-1)^{565}]

[sterile pumice]

Pappa

[inner anchor]

but note that 227 over 11 is -1

yes

try calculating it again

you probably have a similar mistake

np

[wary oasis]

ifI have two coprime rationals $p$ and $q$, is there any way to \emph{compute} the length $n$ of the continued fraction
[
\frac{p}{q} = a_n - \frac{1}{a_{n-1} - \frac{1}{a_{n-2} - ... \frac{1}{a_1}}} ?
]

[sterile pumice]

expectTheUnexpected

[wary oasis]

maybe not really because this is related to the number of steps in the Euclidean algorithm?

[rugged moth]

the number of steps in the euclidian algo will give you the length

[sacred junco]

I guess log p?

[feral vapor]

how to know if a congruence modulo has infinite solution?

[livid birch]

trying to prove that 13|2^70 + 3^70

is there anything im forgetting about x^n + y^n that i can use here

[torn escarp]

I think I'd use fermat's little theorem here to break the exponents down a bit

[livid birch]

oooooo wait i remember that

that’s that p|a^p - a right

[torn escarp]

yeah pretty much

if gcd(a,p)=1 then a^{p-1} = 1 mod p is another way to think of it

[livid birch]

hmmm

[torn escarp]

in your problem you might want to think of it as trying to show $2^{70}+3^{70}=0 \mod 13$

[sterile pumice]

Merosity

[torn escarp]

fermat's little theorem written the way i've put it means you can add or subtract any integer multiple of 12 from the exponent and not change the result

[sterile pumice]

hiyoko127

[twin mural]

or $2^{70}+3^{70}$ is divisible by $2^2+3^2=13$

[sterile pumice]

hiyoko127

[torn escarp]

yeah that factorization seems nicest

[livid birch]

woah

that's so cool

[pearl harbor]

Can I turn $\frac{1}{n\log(n)(\log(\log n))}$ into something simpler?

[sterile pumice]

please request a new nickname

[sacred junco]

Hi

hi who know Triangles and Its Properties

[torn escarp]

not quite

he crossposted #calculus message

[cursive trail]

oop i didnt mean 1/ xd

good catch

[torn escarp]

👍

[celest helm]

So I had this test before and I just want to make sure if option b is right too

For n=4 , n²-1 = 15 which is not divisible by 8

[sterile pumice]

it's Sam

[celest helm]

Am I missing any point here or it's right too

<@&286206848099549185>

Ok np it got sorted out ty

[sacred junco]

damn that is difficult to think about imma do it in the morning

[visual wharf]

elementary school?!?!?!

[topaz ridge]

no

[spare junco]

wait but can't you do n=5, which squared -1 = 24

[celest helm]

We are talking about existance of n

For some even n, (n²-1) will not be divisible by 8

[spare junco]

ohhhhh my bad

[celest helm]

Nah that's fine it got sorted out already

[autumn yacht]

I'm curious as to how you got it sorted. Was it supposed to say 'for all' instead of 'there exists'?

[celest helm]

"For all" would've worked or as teacher said "there exists odd n in N" would've made it false too

[autumn yacht]

Those typos will get you every time

[spare junco]

just asking, but how do you know its referring even numbers instead of odd

[celest helm]

Yeah thats understandable

[celest helm]

They asked if "there exists such n in N"

[sacred junco]

hey there
what is json server ?
and json db ?

[stiff rivet]

this channel is about elementary number theory

[sacred junco]

ohhh sory

[rugged moth]

can $2$ be a primitive root of $2^{2^n}+1$ when $2^{2^{n}}+1$ is not a prime?

[sterile pumice]

Ryu?

[rugged moth]

It can't be if 2^2^n+1 is a prime (n>1), was wondering if it's also true if it's not a prime

[muted drum]

Anyone know how to add 2 negabinary numbers? Im trying to figure out how the carry works

[outer dew]

You add them just like regular binary numbers, except the carry is negative and should be subtracted from each column instead of added to it.

1(carry1) carry1 would be 1011+1110= 110001

the carry1 has negative value

For that last carry1, note that translates to 1 with a positive carry of 1 (as −1 in regular numbers is 11 in negabinary).

This might also help.

https://m.youtube.com/watch?v=h8kXpOMQVj8

[muted drum]

Thx

[simple gyro]

Are all highly composite numbers even.

[sweet mist]

all of them except 1 are.

[true herald]

what does min(a, b) and max(a, b) mean in this scenerio

this server is dead but please I need a bit of help here 😅

<@&286206848099549185>

[sweet mist]

max(a,b) larger of a and b, and min(a,b) is the smaller of a and b. for instance if a=3 and b=4, max(a,b)=4 and min(a,b)=3

and if a and b are equal it's just equal to both of them

[true herald]

why does max(a, b) and min(a, b) change to $a_k + b_k$?

[sterile pumice]

Himeko Takanashi

[true herald]

@sweet mist

[sweet mist]

it will always be the case that either max(a_k,b_k)=a_k and min(a_k,b_k)=b_k or that max(a_k,b_k)=b_k and min(a_k,b_k)=a_k.

In either case, max(a_k,b_k)+min(a_k,b_k) will be a_k+b_k

also, you're supposed to wait 15 minutes of your question being unanswered before pinging helpers

[true herald]

oh ok

thanks!

I understand it more clearly now

[empty falcon]

i have a weird quesiton

consider the squares mod p

p being any prime

for every prime there are only a certain number of results

like for 11, the possible results for n^2 mod 11 would be 0 1 4 9 5 and 3 (where n is any natural number)

put 11 minus those results (mod 11) in a set, so for 11 youd have {0, 2, 6, 7, 8, 10}

just for a clarifying an example, ill show the process of generating a set for 7:
first find all the results for n^2 mod 7 ( you only need to check from 0 to floor(7/2), because you only have to consider numbers from 0 to 6 because mod, but also because n = a will yield the same result as n = 7 - a)
0^2 mod 7 = 0
1^2 mod 7 = 1
2^2 mod 7 = 4
3^2 mod 7 = 2

and to show what i meant about the only checking 0 - floor(7/2)
4^2 mod 7 = 2
5^2 mod 7 = 4
6^2 mod 7 = 1
7^2 mod 7 = 0
its just reverse

so then we take those numbers and subtract them from 7
7 - 0 = 0 (still mod 7)
7 - 1 = 6
7 - 4 = 3
7 - 2 = 5

finally put these results in a set: {0, 3, 5, 6}

[empty falcon]

these numbers describe something special to a problem im working on
they are the smallest numbers k such that p | n^2 + k (k any natural number)

these determine the possible 'starting positions' of when considering a certain erostathenese-seive like construction:

(n^2) + + + + + + + + + + + + + + + + +
2     | 2   2   2   2   2   2   2   2
      | 3     3     3     3     3     3
5     |       5         5         5
      |       7             7

this grid is showing for primes 1 through 4 a possible arrangement of their starting positions as well as a continuation it could correspond to n = 10, or perhaps n = 80 (not sure on that). i dub this arrangement [0, 2, 0, 5], showing the starting positions. the result of this arrangement I am interested is the first time no number-is marked off, which i have shown using a line of |'s on the first plus. soooooo [0, 2, 0, 5] -> 1, because the first plus is not marked off

[empty falcon]

i am interested in every combination of starting positions and what result they correspond to. im not letting zero be a result, because im assuming that n^2 itself (the number 0 corresponds to) would be divisible by n, and so i dont think its very interesting. though, maybe letting it be 0 would make all this easier to analize. Here is an example of the first few combinations.

[0] - 1
[1] - 2
[0, 0] - 1 (I think any arrangement of all 0's makes the result 1)
[1, 0] - 2
[0, 1] - 3
[1, 1] - 2
[0, 0, 0] - 1
[1, 0, 0] - 2
[0, 1, 0] - 3
[1, 1, 0] - 2
[0, 0, 1] - 5
[1, 0, 1] - 2
[0, 1, 1] - 3
[1, 1, 1] - 2
[0, 0, 4] - 1
[1, 0, 4] - 2
[0, 1, 4] - 3
[1, 1, 4] - 2

wow

i did not suspect so many symmetries, i expect them to get distorted down the line

What do you guys think of all this?
please at least dignify the wall of text with a response, sometimes i see people ask big things and get ignored just cause its big

some of my questions about this construction are as follows:

whats the maximum for each size of arrangements? in other words, whats the maximum for the first n primes

what patterns can be found for the sets mentioned above? for example, it can be shown that only sets corresponding to primes congruent to 1 mod 4 can have the prime -1 in the set, because that type of thing has been studied before. I have shamefully little knowledge of number theory results, or just math results in general. what results can be applied to understand this construction that you might know

[visual wharf]

the anwser is 2

[empty falcon]

damn it

[sterile pumice]

NotTheImposter

[empty falcon]

#elementary-number-theory message first message

[empty falcon]

@wooden crater what do you think
did i do a shit job at explaining lol
thats definitely a possibility

[wooden crater]

i’m gonna be real with u chief. u gotta keep it more precise or else nobody is going to want to read what u have to say. i didn’t read it, and id probably have no idea what ur talking about if u did, so i can’t comment on ur explanations. but yea man. just keep it as concise as possible, or ask ur question in bite size chunks, spread out over time

[sacred junco]

I read it and have no clue what you are trying to do

[empty falcon]

damn

then forget that one ill just mess around with it myself

how about this one

i know how to use precise language for this one

consider the numbers coprime to the nth primorial, and then consider the gaps between them

for the numbers coprime to that primorial, how many below the previous primorial (the n-1th primorial) are two apart?

[empty falcon]

is this one clearer lol?

this one i actually know the answer two, but i have similar questions about that more concise construction so im wondering if this wording makes sense before i ask anything else

@rugged moth how about you

and what is kanga gang

[rugged moth]

@empty falcon that's also my question

[empty falcon]

damn

real quick i noticed i fudged the question yet again so here it is

consider the numbers coprime to the nth primorial, and then consider the gaps between them
for the numbers coprime to that primorial that are between 0 and that primorial, how many pairs of numbers are 2 apart
dm me your solution!

and here is an example:

a number a and b are coprime iff gcd(a, b) = 1
a primorial is a product over the prime numbers

so like an example:
30 is the 3rd primorial (2*3*5)
considering the numbers coprime to 30 less than 30, lets take a look at the gaps between them

1, 7, 11, 13, 17, 19, 23, 29,
we can see that 11, 13 and 17, 19 are the only pairs of numbers 2 apart
so for n = 3 there are 2

however, for n = 2
6 is the 2rd primorial (2*37)
considering the numbers coprime to 6 less than 6:
1, 5
there's only one pair of numbers here, and they are 4 apart
so for n = 2 there are 0

i want to see how other solve this because it will probably help me a lot
thats why i want people to dm solutions, so people dont get any part of a solution spoiled to them

i challenge anyone to solve this

good luck, ask questions if needed

[sage fern]

?

jesus christ tf

[empty falcon]

i think this might be the appropriate question to ask

[empty falcon]

how little do you understand in all that

[sage fern]

i think i just about get it

although the typos don't help

but it's just a complex question

and i don't see why it should have any nice answer

[empty falcon]

oh it has a beautiful answer

like
how the fuck did that happen answer

[sage fern]

oh ok

in that case i just don't know enough number theory to attack it properly

[empty falcon]

the amount you need is suprisingly small
its more about the direction you take

[sage fern]

huh

actually yeah i see something now, it's the primes and the coprime

duh

i might try it later

[empty falcon]

but yes the less you know the hard it will be regardless
i spend a lot of time thinking about it visually, and because of that 70% of my proof is just logic

yeah because it got blown out:
#elementary-number-theory message
challenge question

[wooden crater]

is the answer the (n-2)th prime?

[empty falcon]

why would it be that

[wooden crater]

i just guessed lol

for n = 3, it was 2

for n = 2, it was 0

[empty falcon]

i figured

well i mean
you kinda have to have a proof as to why your thing works
not nessesarily rigourous but

[spark stirrup]

Are we supposed to include 1 in the list of coprimes?

@empty falcon

[empty falcon]

yes

as in the example

[split relic]

can some one explain me this please

[sacred junco]

hii

what is your age

hahaha

[willow jungle]

Forward from #discussion:

Is there a name for sets of numbers such that the sum of the two smallest elements is greater than the largest element, the sum of the three smallest elements is greater than the sum of the two largest elements, the sum of the four smallest elements is greater than the sum of the three largest elements… and so on?

If they don't have a name, how can I define the set of all sets of this type?

[stiff rivet]

highly doubt there is a name for that

you define it by saying that?

[willow jungle]

ok then, it's easier than writing a thesis about it just to name it

[fresh hound]

If you have $x^2 - 1 \equiv 0 \mod{p}$ with gcd(x,p)=1 and factor into $(x+1)(x-1) \equiv 0 \mod{p}$, can you conclude that $x+1 \equiv 0 \mod{p}$ or $x-1 \equiv 0 \mod{p}$?

x is integer

[sterile pumice]

beachcow

[stiff rivet]

a product of two numbers is only divisible by a prime p, if one of the factors already is, right? @fresh hound

[fresh hound]

yes

[stiff rivet]

thats this statement only more general

[fresh hound]

Ok i see

but in this case, if one statement is true for one factor, then other is not

since x+1 \equiv 0 cannot be true if x-1 \equiv 0, right?

[stiff rivet]

sure

well, its true for p=2

[fresh hound]

i forgot

p is odd in this case

[stiff rivet]

then 1 is never equivalent to -1 mod p

[fresh hound]

Ok

[compact moth]

Are there any proofs on all integers being products of

x, where x is in the range [1,10]
and
2^n, where n is in the rnage [0,infinity]

I.e

For any y in doubleZ,

y = x * 2^n?

What about just

y = x^n?

[stiff rivet]

no, its not true

[abstract flax]

Can you give an exact statement of what you are trying to prove? This doesn't seem true

[compact moth]

It really isn't formal, just something I'm curious about:

Our number system is based on 1-10 (or 1-9?)

Is every number then a potenciate of these 10/9 base numbers?

[abstract flax]

potenciate?

[stiff rivet]

no, smallest counterexample: 11

[compact moth]

Don't know the word.

Like a product but for potency

Oh yeah, primes...

But if were to take out the primes?

[stiff rivet]

11^2

also many other numbers

like 5*3^2

[compact moth]

hmm...

[abstract flax]

The only numbers that are products of 1-9 are numbers of the form 2^n 3^m 5^p 7^q, if you include any other prime numbers in the prime factorization, then it fails. Although I'm not sure if this is what you are asking.

[stiff rivet]

something like that anyway

[compact moth]

It is.

[stiff rivet]

the way we write down our numbers in decimal has no connection to how numbers can be represented as products of other numbers

the latter makes no mention of the decimal system

like most (all) statements in number theory

[compact moth]

Alright.

I will take your points with me, and go back to the drawing board. Thank you for your help 🙂

[stiff rivet]

(in general questions that depend on the decimal system are considered "bad")

[patent escarp]

Is there a way to test if a multivariable polynomial has any rational roots?

I have a 4 variable quartic polynomial and I want to solve for rational zeroes (if there are any), but It’s very long and I don’t think I can just brute force.

The polynomial is $$4q^{4}x^{2}y^{2}-8q^{4}x^{2}z^{2}+4q^{4}y^{2}z^{2}-8q^{3}x^{3}y^{2}+16q^{3}x^{3}z^{2}-8q^{3}xy^{2}z^{2}+4q^{2}x^{4}y^{2}-8q^{2}x^{4}z^{2}+8q^{2}x^{2}y^{2}z^{2}-8q^{2}y^{4}z^{2}+4q^{2}y^{2}z^{4}-4qx^{3}y^{2}z^{2}+8qxy^{4}z^{2}-4qxy^{2}z^{4}+x^{4}y^{2}z^{2}-2x^{2}y^{4}z^{2}+x^{2}y^{2}z^{4}=0$$ if that helps.

[sterile pumice]

Chixen

[patent escarp]

There’s no constant term so ik 0 is a solution but I want solutions where each is unique

also if y is 0 there are some more trivial solutions.

but I want nontrivial ones as stated above.

idk if this is supposed to be in advanced but I didn’t think so bc it’s literally a polynomial.

[patent escarp]

Should I repost in the advanced channel?

[patent escarp]

I’m always open for help, so even if five days have passed, if I haven’t posted my solution here, I still need help.

[patent escarp]

still open

[cursive trail]

not that i know of

[patent escarp]

I know there’s no general solution to the general case, but I’m looking at this one in particular.

I also know that at least one solution exists, but I’m not sure of any others. I also don’t know what the existing solution is.

I think I can find the existing solution quickly

I’ll do it when I have access to a computer

[balmy sail]

Hello, I i have tried to break following type of cipher: Every printable ascii number (let say - x) is encoded in the following way: (ax+b)^e (mod n)
(It looks like affine cipher superposed with exponentation cipher). I know e and n - its 101 and 97, respectively, I need to find a and b. I do not want the strict answer, but this is solvable in some way? If yes, based on what laws/lemmas etc. I have tried to find a and b coeff by brute force and use Diffie - Hellman method for exponentation part but it fails. Thanks in advance.

[rugged moth]

are 97 and 101 a prime?

[celest helm]

[balmy sail]

Yes they are

[rugged moth]

so can you not like find the inverse of e mod(phi(101))?

[balmy sail]

101^ -1 (mod 100) = 1 am i right?

[rugged moth]

?

you mean $101^{-1}\equiv 1 (\mod 100)$?

[balmy sail]

Yes

[rugged moth]

Yes

lol

you statement is equivalent to saying $1^{-1} \equiv 1$

[balmy sail]

What? $1 * 101 \equiv 1 (\mod 100)$ isn’t it?

[sterile pumice]

KuchiChan

[glad junco]

so 101*1 = 101, kay. then 101 / 100 goes into it one time with a remainder of what?

yes its 1

[wary oasis]

~~
If I have positive integers $a,b,c,d$ with $(a,b) = (c,d) = 1$, and further
[ \frac{a}{b} = \left\lceil \frac{c}{d} \right\rceil - \frac{c}{d}\ ,]
how can I conclude that $b = d$?~~

If I have positive coprime integers $c, d$, why are $d \left\lceil \tfrac{c}{d} \right\rceil - c$ and $d$ also coprime?

[sterile pumice]

expectTheUnexpected

[dusty dragon]

If x | (a + b) and x | a, then x | b.
So suppose that gcd(d * ceil(c/d) - c, d) = x. Then x | d and x | d * ceil(c/d) - c. But this implies that x | -c which means that either x | -1 or x | c. If x | -1, then x = 1. If x | c, then x | gcd(c, d). But gcd(c, d) = 1 so x = 1

Perhaps something like this? In fact, you can prove a more general result by replacing ceil(c/d) with some arbitrary integer a

[wary oasis]

I see, cool. With your strategy we should even have:
Let c,d,n,m be integers, and assume d divides n, but no divisor of d divides m.
Then gcd(n + m c, d) =< gcd (c, d).
Not so surprising :D

[pearl hatch]

Hello everyone. I am planning to do research in number theory, but don't have a topic. Suggestions would be much lower.

[stiff rivet]

research?

[quaint timber]

Hi could someone help me with this problem please?

I reduced it to [a] + [23][y] = [33] but I don't know where to go next

[quaint timber]

<@&286206848099549185>

[dusty dragon]

Remind me what [x] is in this context

[quaint timber]

a variable for a congruence class mod 35

is anyone able to help pls?

[torn escarp]

you'll want the determinant to be 0 mod 7, otherwise you'll only have 1 solution

or no solutions

of course you also want the determinant to be nonzero mod 5 so

I think there can only be 4 choices for a that work out

[torn escarp]

to maybe be a bit more clear, instead of solving it mod 35, instead look at it mod 5 and mod 7 and solve there individually, you'll notice something peculiar when you simplify it down mod 7. Then you are guaranteed the ability to combine your solutions back with the chinese remainder theorem in principle, but there's no reason to do that for the sake of counting solutions here which is nice

[analog onyx]

I am trying show that there are an infinite number of integer solutions to ax + by = c where a and b are integers >= 1, c is an integer >=0, and gcd(a,b) = 1.

I have applied bezouts identity to show that we have a solution, but i’m not sure how to get that to infinitely many

[wooden glen]

Note that you can add b to x and subtract a from y without changing the sum on the left.

[analog onyx]

I see that

so we can arrive at infinitely solutions by having a(x+bn) + b(y-an) = c

[wooden glen]

Eyup.

[analog onyx]

can i get some opinions on this?

mainly on if my approach to the proof was right and if the proof is correct

[analog onyx]

<@&286206848099549185>

[visual oracle]

help

[bleak igloo]

Can i use the same "clock" logic of $\mathbb{Z}{3}$ into $\mathbb{Z}{4}$ or larger $\mathbb{Z}$ ?

[sterile pumice]

Guilhotina

[rugged moth]

what do you mean by 'into'?

homomorphism?

[bleak igloo]

for Z4

[rugged moth]

so a typo?

[bleak igloo]

sorry for bad words

[rugged moth]

yes

[bleak igloo]

yeah

[rugged moth]

modular arithmetic

[bleak igloo]

so the logic is the same for every Z ?

[rugged moth]

for every Z_m, yes

[bleak igloo]

ok

[sacred junco]

is xRy, xRz, then yRz transitive ? (for all x,y,z ∈ X)

[amber depot]

No it's if xRy and yRz then xRz, this is the transitivity property

[analog onyx]

xRy, yRz, then xRz

[sacred junco]

yea, just tested it doesn't work. thanks

[patent escarp]

What strategies exist to find diophantine solutions to a polynomial with many variables? I know there isn’t any known general case, but I was wondering if there are some things I could try.
I’m more specifically trying to find when $$\sqrt{\left(2xy\left(x-y\right)\right)^{2}+\left(z^{2}\left(2x-y\right)\right)^{2}}$$ is an integer for coprime inputs of x, y, and z, but I don’t think this exact expression is special in many ways.

[sterile pumice]

Chixen

[sacred junco]

@patent escarp since it's a sum of squares the only solutions will be a subset of the solutions to finding Pythagorean triples

[patent escarp]

I have a list of solutions I'll send the txt file rq

ima tweak the code to only send nontrivial solutions

[sacred junco]

If we call this number c, and 2xy(x-y) is a and z^2(2x-y) is b, then we can find solutions for a and b from the set of Pythagorean triples given by (a, b, c)
There are good generating formulas for these

And conditions saying which can take on what values

[patent escarp]

ok I got the new list

for numbers up to (100,100,100)

heh strange how theres exactly 750.

[sacred junco]

From those nice generating things, since 2xy(x-y) is even it will have to equal 2mn for coprime m,n of different parity, say n>m.
And z^2(2x-y) will only have odd solutions since that forces it to be n^2-m^2

[patent escarp]

ok

this means that z must be odd, but (1,3,4) is the smallest solution.

I'm not asking for coprime m,n. I'm looking for coprime x,y,z. Some coprime x,y,z generates n,m with a gcd greater than 1.

[sacred junco]

Yeah that's the issue

Cool

[patent escarp]

I just thought of something small.

[sacred junco]

All of those solutions are parametrized abritrary gcds times the coprime sets then, so one can still use the stuff about Pythagorean triples

[patent escarp]

nvm i was right

the (2x-y) can just be replaced with (y) and the solutions are pretty much the same

it just simplifies things

this means we can factor out (2x-y) from the whole thing, which is probably where m and n not being coprime came from.

wait no I forgot how I was doing that

ooh yeah because though (x-y)^2 doesn't change if you set y to (2x-y), (2xy(x-y))^2 does change because of the extra y mb.

[patent escarp]

Anyone else have anything to add?

well I found that $$z=\sqrt{\sqrt{2xy}\left(x-y\right)}$$ works.

[sterile pumice]

Chixen

[patent escarp]

that could be of use.

no it doesn't.

mb

maybe I mistyped. $$z=\sqrt{\sqrt{\frac{xy}{2}}\left(x-y\right)}$$ should work.

[sterile pumice]

Chixen

[patent escarp]

nope. Idk what im doing wrong.

[patent escarp]

ok ok it's easier than the above I think (I hope)

It works for x and y where $$\sqrt{\frac{xy}{2}}\left(2x+y\right)$$

[sterile pumice]

Chixen

[patent escarp]

specifically "if", not "if any only if"

[patent escarp]

The other solution I found was $$z=2\sqrt{\frac{\sqrt{xy}^{3}}{2x-y}}$$

[sterile pumice]

Chixen

[patent escarp]

which is pretty uncommon so I prefer the first one

idk if that's the only solutions tho

It works when $$\frac{\left(xy\right)^{3}}{\left(2x+y\right)^{2}}$$ is a perfect fourth

[sterile pumice]

Chixen

[patent escarp]

so 2x+y must be a square and xy must be a fourth

[raven moon]

did you explore what the person above was saying at all

about pythagorean triples?

[patent escarp]

That’s how I got the expressions

[raven moon]

ah

yea im not sure, sorry

i think you might be ahead of me tbh

[patent escarp]

I solved for z when the first term is the n^2-m^2

Well I was just hoping someone would have ideas

[raven moon]

i mean other than coding im not really sure

is there something like oeis for triples

can you use oeis for triples

then you might be able to work backwards

[patent escarp]

because I think if I can find the answer to this I can find solutions to the square of squares unsolved problem

I have a method that may or may not work

I want to analyze the solutions to the question then I can use the answers to the square of squares problem

[raven moon]

im sorry

[patent escarp]

So far from what I’ve found I can generate (maybe idk) infinite solutions with six squares

As well as solutions where all but one diagonal works

but so far only one with seven and it’s the one we already know :(

[raven moon]

i really wish i could help lol

[patent escarp]

It’s fine, I think I can attack it some other way

It’s been fun exploring this because it is a surprisingly involved problem

I’ve even found a way to geometrically represent the problem. If a set of points with specific conditions are met then you can easily solve the problem.

[torn escarp]

what/where did this problem originally come from

[patent escarp]

Look up “Magic square of squares” I have a method that, if this much easier problem is solved, then you can find solutions to a magic square of squares.

It’s an involved method and it doesn’t always work, so I want to find all solutions so I can analyze the solutions to find if there is some value that works.

[torn escarp]

from searching it looks to be an unsolved problem

[patent escarp]

I know that at least one solution works, but idk if more than one solution works

[patent escarp]

yes

[torn escarp]

wdym, you know one solution? or just that you've proven nonconstructively that at least one must exist

[patent escarp]

No, when I mean a solution to the problem, I mean a square with at least 7 of the values inside of it being a perfect square.

All I really care about is a solution with 7/9 perfect squares

My algorithm always gives 5/9, it gives 6/9 for solutions to $$\sqrt{\left(2xy\left(x-y\right)\right)^{2}+\left(z^{2}\left(2x-y\right)\right)^{2}}$$ and exact one solution so far gives 7.

[sterile pumice]

Chixen

[patent escarp]

I want to find a second solution that gives 7.

7/9*

[torn escarp]

gotcha

[patent escarp]

I could be wrong but iirc the seed that gives 7/9 is (385,275,198)

and it’s a solution that is already known about

[amber depot]

Suppose we have the integers modulo m, why do we suddenly stop considering its elements as congruence classes and start treating them as if they were actually integers instead of sets?

[torn escarp]

because any representatives of a given equivalence class are interchangeable

it's just convenient to write a number

[keen vault]

Does anyone know what the smallest (or smallest known) efficiently computable superset of prime numbers is? For example, you could take the set of all odd numbers and 2, and all prime numbers are in that set. However, that set is pretty big. Is there a smaller set?

[wooden glen]

Define "efficiently computable". Since PRIMES is in P, it's pretty tempting to declare that set itself to be "efficiently computable".

[sage fern]

define 'smallest'. any such set will be countably infinite, as it must contain the primes, which are countably infinite.

[sacred junco]

I mean yeah but I assume they mean small wrt containment

[sacred junco]

This question smells like it's leading to the various kinds of pseudoprimes out there

Because that's basically exactly the concern when talking about pseudoprimes of some kind of primality test

[keen vault]

Smallest asymptotic growth rate of the set relative to the set of primes. If you choose the set of primes, you get “1”.

[sacred junco]

iirc often primality tests are ranked by how fast they are and also separately by how small the natural density of pseudoprimes is

Which gives you a nice a la carte of what you are asking for, so I'd start by looking up all the currently known best primality tests for speed or for low natural density of pseudoprimes

Haha here's a fun one
The primes union the Miller test pseudoprimes is just the primes if the generalized Riemann Hypothesis is true

[patent escarp]

Ok I’ve narrowed down my previous question to something simpler. What integer value of y in terms of x and z make both $$\sqrt{\frac{2x^{2}-2z^{2}+y^{3}}{y}}$$ and $$\sqrt{2xz\sqrt{\frac{y}{2x^{2}-2z^{2}+y^{3}}}}$$ integers?

[sterile pumice]

Chixen

[patent escarp]

I think it’s simpler at least because you’re only solving for one variable and not 3, despite the expressions themselves being more complicated.

Not an integer but $$\sqrt[3]{\left(x+z\right)^{2}+\left(x-z\right)^{2}}$$ works for the first one

[sterile pumice]

Chixen

[patent escarp]

bc difference of squares

which simplifies to $$\sqrt[3]{2\left(x^{2}+z^{2}\right)}$$

[sterile pumice]

Chixen

[patent escarp]

wait no it just makes the top half a square forgot about the $\frac{}{y}$

[sterile pumice]

Chixen

[patent escarp]

I realize now that the second expression is decreasing asymptotically and doesn’t always hit an integer coordinate.

[keen vault]

sorry I left the question ambiguous and it’s still going to be a little bit ambiguous for the moment. The computation constraint has to do with the set itself. It’s not enough to polynomial time evaluate whether some number is in the set (although you have to be able to do that as well) - you also need to be able to generate the set efficiently as per https://en.m.wikipedia.org/wiki/Formula_for_primes @wooden glen

By my measure, normal properties of an efficiently computable set need to include both the ability to evaluate whether an item is in the set or not and enumerate the set.

[patent escarp]

I don’t remember exactly but I think I once saw this numberphile video on something called whiteness numbers. I think could be helpful.

[keen vault]

witness numbers not whiteness 😅

[patent escarp]

I use the swipe thing on my phone keyboard and apparently rly whiteness made more sense according to my phone and I did not notice.

[visual oracle]

hi

🙂

[wheat tinsel]

What is a useful criteria to determine if an arithmetical function is multiplicative?

[torn escarp]

check f(1)=1, check it has the form for prime p that f(p^k) well defined, since it's a product of how it's defined on powers of primes

another criteria is if its dirichlet series has an euler product is equivalent to being multiplicative

I guess another criteria is if you can write it as a dirichlet convolution of other multiplicative functions, it's multiplicative, they form a group

[wheat tinsel]

I don't understand this: "check it has the form for prime p that f(p^k) well defined".

Another criteria might be if you can pick a multiplicative function which you can convolute with the other function to obtain a simpler function, then if the convolution is multiplicative, it follows. But that seems unlikely in most cases, idk

Since the convolution might be simpler, checking multiplicativity is probably easier, but dunno

[torn escarp]

if it's multiplicative then you can write it as $$f(n) =\prod_{p|n} f(p^k)$$

[sterile pumice]

Merosity

[torn escarp]

like for instance, $\phi(p^k) = p^k-p^{k-1}$ or $\sigma(p^k) = \frac{p^{k+1}-1}{p-1}$ etc, working this out and making sure it is valid when you multiply them together

[sterile pumice]

Merosity

[wheat tinsel]

Its easy to derive the formula $\phi_k(n)=n^k\sum_{d|n}\mu(n/d)\frac{1^k+\cdots +d^k}{d^k}$ where $\phi_k(n)$ denotes the sum of the kth powers of the numbers below n and relatively prime to n.

[sterile pumice]

Jacked

[wheat tinsel]

I was wondering if you could use Faulhberg's formula or some other procedure to derive a more closed form. I don't know what to search for in the internet for this

And $\mu$ is the möbius function, of course

[sterile pumice]

Jacked

Jacked

[torn escarp]

this formula looks wrong to me, that sum doesn't look right, should be $$\phi_k(n) = n^k \sum_{d|n} \frac{\mu(d)}{d^k}$$

[sterile pumice]

Merosity

[torn escarp]

if you are writing $$\sum_{d|n} \mu(n/d) \sigma_k(d)$$ this is equal to the convolution $$\mu \star \sigma_k = \mu \star u \star N_k = N_k$$ here I'm using the fact that $u(n)=1$ means $\mu \star u$ are inverses so you get the identity and $N_k(n)=n^k$.

[sterile pumice]

Merosity

[torn escarp]

further still if you're trying to derive $$\phi_k(n) = (\mu \star N_k)(n) = \sum_{d|n} \mu(n/d)d^k$$ then because these are multiplicative functions you can work out what it should be for just a prime power, so $$\phi_k(p^a) = (\mu \star N_k)(p^a) = p^{ka}-p^{k(a-1)} = p^{ka}(1-\frac{1}{p})$$ so together you can combine them to get, $$\phi_k(n) = n^k\prod_{p|n}(1-\frac{1}{p})$$

[sterile pumice]

Merosity

[torn escarp]

this is called Jordan's totient function if that helps you search, also it's Faulhaber not Faulberg 😛

[patent escarp]

I played around with perfect numbers a bit and found this formula for the sum of divisors:
$$D\left(\prod_{i=1}^{∞}p_{i}^{q_{i}}\right)=\prod_{i=1}^{∞}\frac{p_{i}^{q_{i}+1}-1}{p_{i}-1}-\prod_{i=1}^{∞}p_{i}^{q_{i}}$$

[sterile pumice]

Chixen

[patent escarp]

where p is the list of all primes.

and q is the list of the powers in the prime factorization (ending in infinite zeros, of course.)

ah damn, it already has been found.

I don't know why I only looked up if it already existed after I had already made the function.

$\prod_{i=1}^{∞}p_{i}^{q_{i}}$ is a perfect number if and only if $\prod_{i=1}^{∞}\frac{p_{i}^{q_{i}+1}-1}{p_{i}^{q_{i}+1}-p_{i}^{q_{i}}}=2$

[sterile pumice]

Chixen

[charred pasture]

.help

[rotund gust]

Commands:
clopen: .close, .reopen
factoids: .tag
help: .help

Type .help <command name> for more info on a command.

[charred pasture]

,help

[sterile pumice]

A brief description and guide on how to use me was sent to your DMs!
Please use ,list to see a list of all my commands, and ,help cmd to get detailed help on a command!

[charred pasture]

,help frac

[sterile pumice]

Command frac not found!
Use the ,list command without arguments to see a list of commands.

Dec 20, 2021, 1:34 PM

[charred pasture]

,list command

[sterile pumice]

No matching modules! See ,ls for a list of modules and their commands.

Dec 20, 2021, 1:34 PM

[charred pasture]

,ls

[sterile pumice]

My commands!

LaTeX Rendering

autotex, ctan, guildpreamble, preamble, tex, texconfig, texdoc

Guild Admin

autoclean, config, disable, editrole, forgetrolesfor, rmrole

Info

avatar, channelinfo, guildinfo, roleinfo, rolemembers, userinfo

Utility

giveme, notifyme, rotate, time

Moderation

ban, kick, mute, note, preban, prune, tickets, unban, unmute

Mathematics

calc, nlab, query

Meta

about, feedback, help, invite, list, ping, prefix, support

Use ',help' or ',help cmd' for detailed help, or get support with ,support.

[wheat tinsel]

I think you are getting confused (or I'm wrong, which might be). Jordan's totient generalization of Euler's is not the same as the function I was considering (which is definitely not multiplicative). The expression you gave for Jordan's totient is right, though again is not the same function

For the function I was considering, then you just have to apply Möbius inversion formula for the expression I gave

[torn escarp]

yeah I actually give 3 separate answers because it was slightly ambiguous to me what you were saying

I didn't know what $1^k+\cdots+d^k$ represents, could be $\sum_{h|d}h^k$ or $\sum_{h=1}^d h^k$

[sterile pumice]

Merosity

[wheat tinsel]

mb

[wheat tinsel]

$\int_e^x\log(\log t)dt=x\log(\log x)-\int_e^x\frac{1}{\log t}dt=x\log(\log x)+C-Li(x)$, but we know $Li(x)=x/\log x+O(x/\log^2x)$. Can I conclude $\int_e^x\log(\log t)dt=x\log(\log x)-x/\log x-O(x/\log^2x)$?

[sterile pumice]

Jacked

[wheat tinsel]

I haven't seen big Oh's used like that (subtraction), but I assume that would be equivalent to $x\log(\log x)-x/\log x-\int_e^x \log(\log t)dt=O(x/\log^2x)$, which makes sense.

The exercise asks me to give an estimation in terms of O(x/logx), so I'm a little confused

[sterile pumice]

Jacked

[wheat tinsel]

idk if that makes sense

[wheat tinsel]

Btw I did realize it's ok, but you just write +O(x/log^2x)

[sacred junco]

Hi, do you know any book to start with number theory?

[sleek cove]

yes i do

[sacred junco]

why must n_0 be prime

and if n_1 and n_2 are less than n_0 they don’t necessarily need to be integers, but why is their norm 1?

is it because n_0 is the least such integer such that ||n_0||<=1

so if there are integers less than n_0 then they are >1

so my guess is n_1,n_2 are integers with norm greater than 1

but they cant both be because of multiplicity of the norm meaning norm(n_0)=norm(n_1n_2)=norm(n_1)norm(n_2)

[torn escarp]

they are necessarily integers by assumption

we know n_0 is prime because any larger number will factor into smaller integers

and we know for all integers |n|<=1 from the start

[torn escarp]

this case never happens since the enitrety of case (ii) occurs with all integers |n|<=1

[sacred junco]

wait wtf

why are there only two cases of n>1 and n<=1?

norm is continuous

thats prolly why

nah nvm

first case was that there exist integer with norm>1 and second case is all integers have norm <=1

i guess thats the negation?

[torn escarp]

no, there are absolute values of Q that have all integers bounded above where they're less than or equal to 1

they're the p-adic absolute values

that's what you're proving, ostrowski's theorem shows the only norms on Q are exactly the trivial one, the real one, and for each prime a p-adic one

up to equivalence

[sacred junco]

yeah i know thats the goal of the proof

but what case do norms with n>1 for all integers n nonzero or why doesnt this case exist

ig how are these two cases the only ones needed to be checked

i know what the theorem is stating but if I didnt wouldnt it make sense to cover all possible cases?

[torn escarp]

these are all of the cases

either at least one integer is >1 or all integers are <=1

this second case only deals with when all integers have norm <=1

[sacred junco]

ok ig i see it

my question was why cant all integers be greater than 1

but that falls into case 1

because 1 generates all ints anyways

so that would mean norm 1 > 1 automatically implying norm n> 1

norm 1 equals 1 tho

always

[torn escarp]

yup

[sacred junco]

Let a, b positive integers such that b>a>=2 and gcd(a+k,b+k)=1 for any k\in{1,2,…,b-a}, prove that a and b are consecutive

[wooden glen]

Yes?

[empty owl]

If you don't know where to start, think about what it means to say a and b are consecutive.

[analog onyx]

I think i should start by using the definition of even and odd integers but im not sure where to go after that

this is our definition of a minimal solution, a definitely least solution is a solution which is minimal wrt x and y

[empty owl]

Choose a = 2 and b = 1 then see what choices you have for c in Lemma(1), then apply the definition and see where the solutions x and y are at in their inequality.

[analog onyx]

the definition as in?

oh of the minimal solution

[empty owl]

yep

[analog onyx]

how can i use lemma 1 without proving it though

[empty owl]

My bad, i misinterpreted what you said, I didn't realize that you were trying to prove it.

[analog onyx]

yes i guess i should have mentioned that

is that still the same approach or no

bc i think i need to take arbitrary a and b

[empty owl]

Essentially, set a = 2k and b = 2k + 1, plug those in and compute what the inequality yields, i believe you get 2 values from it.

[analog onyx]

okay but how do i go from my statement being an equality to an inequality

like i have 2kx + (2k + 1)y = c

[empty owl]

0 <= c < (1/2)a+b -> 0 <= c < (1/2)(2k)+(2k+1) -> 0 <= c < 3k+1 , thus, assuming c is an integer, the values for c are 0 and 3k.

[analog onyx]

i follow that, c is an integer so we get c is either 0 or 3k

i just dont understand how that helps us prove lemma 1 since we are starting with lemma 1 and arriving at c = 0, 3k

do we then apply the definitions of a minimal solution?

[empty owl]

You're starting at the assumption that a and b are even and odd, respectively, and that a and b are coprime (relatively prime).

[analog onyx]

yes

what does the value of c either being 0 or 3k tell us though

[empty owl]

If ax+by=0, with a and b coprime, what does that say about x and y?

[analog onyx]

ones positive and one is negative?

[empty owl]

And vice versa

[analog onyx]

yes wlog

[empty owl]

So we know that x and y both have a positive and negative solution, how else could you manipulate the equation to fit the definition?

[analog onyx]

take the absolute value of both x and y

[empty owl]

Make the equation fit the parameters of the definition, think about where |x| and |y| live.

[analog onyx]

they have to lie between a and b correct

for example with 3x + 5y = 4, our minimal solution is (-2, 2)

maybe that is not always true though

[empty owl]

Well in this case |x| <= 5/2, which means -5/2 <= x <= 5/2, since x is an integer, we can see that the minimum solution for x is -2.

[analog onyx]

well it could be -1, 1 or 2 as well

but then we would not find a minimum solution for y with -1, 1 or 2

[empty owl]

Correct, x=-2 renders the smallest solution for x. For y, expand |y| <= 3/2, from there it would only give us (3,-1)

Messed that up

[analog onyx]

well couldnt y also be -1, 1

[empty owl]

Yes, but i believe the definition is only concerned with how large x and y are in their respective solution sets.

[analog onyx]

oh we have no integer solution if y is 1

i understand all of this but i am not sure how to put this all together for a proof

[empty owl]

We got to the point that ax+by=0, try multiplying both sides by 2/ab, keeping in mind that x and y have both positive and negative solutions.

[analog onyx]

(2/b)x + (2/a)y = 0?

[empty owl]

Yes

[analog onyx]

(2/b)x = (-2/a)y

[empty owl]

If x = -b/2 , then y = a/2. If x = b/2, then y = -b/2. Thus -b/2 <= x <= b/2 and -a/2 <= y <= a/2 -> |x| <= b/2 and |y| <= a/2, fitting the definition.

[analog onyx]

oh okay i was being dumb okay

[empty owl]

I was trying to nudge you, but its okay 🙂

[analog onyx]

i forgot what i was trying to show

[empty owl]

I understand, you can get lost easily in these proofs.

[analog onyx]

so we showed that we have a minimal solution to ax + by = 0 right

actually a definitely least solution

[empty owl]

Correct, thus satisfying lemma(1).

[analog onyx]

omg okay wait

so we showed that c had to either be 0 or 3k

[empty owl]

Correct

[analog onyx]

so we have ax + by = 0

and then we showed that we have a definitely least solution for that

[empty owl]

But 3k > 0

Well okay, actually yes its required to show, but just use the same reasoning.

[analog onyx]

yes so we must show it is also true for c = 3k

[empty owl]

Yup, but just use the same approach.

[analog onyx]

how does it differ since we get a 6/(ab) on the rhs

or do we not multiply both sides by 2/(ab) but rather something different

[analog onyx]

and how do we know c isnt k or 2k for example

[empty owl]

So backing up for a sec

Lemma(1) states that ax+by=c has A definitely least solution, so just one. (Nevermind, i keep getting this confused).

[analog onyx]

for every c though

[empty owl]

The reason that c is either 0 or 3k is due to the division algorithm. For all integers with divisor 3, you will have a remainder of 0,1, or 2, thus making c = 3k, 3k+1 , 3k+2. Since in the inequality c can be 0, you're left with c=3k.

[sacred junco]

b=a+1, next?

[empty owl]

What does it mean when a and b are consecutive? Think of the factors they share.

[sacred junco]

I dont know

[empty owl]

What common factors do 2 and 3 share?

[sacred junco]

1

But we dont know if they are consecutive, we need to prove that

[empty owl]

Right, and since 3 comes after 2, 2 and 3 are consecutive integers, with gcd(2,3)=1

And yes,we don't know that they are consecutive.

But we do know that 2 consecutive integers a and b will be coprime with gcd(a,b)=1.

[sacred junco]

Yeah

[empty owl]

We can start the proof by assuming that a and b are coprime.

[sacred junco]

But we already know (a+k,b+k)=1, for every k\in{1,2,…,b-a}, if we let b=a+t we have
gcd(a+k,t)=1<=>
gcd(a+1,t)=gcd(a+2,t)=…=gcd(b,t) and from there i think we need to show that t=1

[empty owl]

Start with this, assume that gcd(a,b)=1 -> ax+by=1, then use induction.

[analog onyx]

how do i find the magic quantity to multiply by in the c = 3k case, like for c = 0 we used 2/(ab)

[sacred junco]

If gcd(a,b)=1 then gcd(a,a+t)=1=gcd(a,t)=1,
but we know gcd(b,t)=gcd(a+t,t)=gcd(a,t)=1, then gcd(a,a+t)=gcd(a,b)=1

So gcd(a,b) is 1, but how do we prove they are consecutive

[empty owl]

Ok, in order to prove that a and b are consecutive we must show that b = a + 1. Assume that gcd(a,b)=1 -> ax+by=1. By induction, let k = 1 giving us gcd(a+1,b+1)=1 -> (a+1)x + (b+1)y = 1 -> ax + x + by + y = 1 -> (ax+by) + (x+y) = 1 -> 1 + x + y = 1 -> x=(-y). Plugging this back into the original equation we have (a+1)(-y) + (b+1)y = 1 -> (-a-1+b+1)y=1 -> (b-a)y=1 -> (b-a)|1 -> b-a = (+-1) (this is possible by your divisibility theorems, and since b>a>=2, b-a will always be positive) -> b-a = 1 -> b = a+1

Same approach to show for k \in S -> k+1 \in S.

[sacred junco]

Okay i understand

[sacred junco]

Wdym

[empty owl]

We are proving this using induction, so you have to assume the statement is true for k and then show its true for k+1.

We just shown for k=1, the first part.

[sacred junco]

Oh i understand

Thanks

For k+1, we have gcd(a,b)=1 and gcd(a+k+1,b+k+1)=1<=>
ax+by=1, (a+k+1)x+(b+k+1)y=1?

[empty owl]

Correct, but at this point i wouldn't worry so much about gcd(a,b)=1, its more about assuming and using gcd(a+k,b+k)=1.

[sacred junco]

ax+kx+x+by+ky+y=1

ax+by=1
x+y+kx+ky=1

[empty owl]

You're not assuming that the statement is true for k, go back over what induction states then revisit the problem.

[sacred junco]

But i think we dont need induction because we already know (a+k,b+k)=1 and (a,b)=1 so from that we need to show that b=a+1, but also (a+k-1,b+k-1)=1, so we have:
(a+k-1)x+(b+k-1)y=1 and
(a+k)x+(b+k)y=1 and from substracting these we have x=-y, now x(a-b)=1 <=> a-b=-1 <=> b=a+1

a-b=-1 because b>a so a-b is negative

[empty owl]

How can you assume that gcd(a+k-1,b+k-1)=1 ? You've only assumed 2 things, gcd(a,b)=1 and gcd(a+k,b+k)=1.

If you want to go that route, use strong induction.

[sacred junco]

You are right

:))sorry

[empty owl]

Its k (:

[sacred junco]

one more question, if gcd(a,b)=1 and gcd(a+1,b+1)=1 we have the same x and y s.t ax+by=1 and (a+1)x+(b+1)y=1?

[empty owl]

Yup

But remember, the x and y in a linear combination is chosen for the particular solution.

In this case, any multiple of a and b are of same value with differing parity.

[sacred junco]

Thanks a lot, but why are x and y the same?

[empty owl]

By virtue of a and b being consecutive integers and gcd(a,b)=1, since ax+by=1 -> a(-y) + by = 1 -> (b-a)y=1 -> (b-a)|1

So those particular integers are necessary for the conditions put in place on a and b.

[sacred junco]

No, i mean why if gcd(a,b)=gcd(a+1,b+1)=1 we have ax+by=1 and (a+1)x+(b+1)y=1, why are x and y the same in the both equalities

I know ax+by=1 from bezout lemma but from gcd(a+1,b+1)=1 we dont have (a+1)z+(b+1)t=1 with {z,t} not {x,y}?

Wait, i think (a+1)z+(b+1)t=1 for any z, t include x, y so we can choose z=x and t=y

[empty owl]

Yup, but even if you had them as different integers, ax + by = (a+1)z + (b+1)t -> ax + by = az + bt + z + t, in the case of az+bt, a and b are still coprime, so az+bt=1, so we get z=-t, which leads us to the same conclusion.

[sacred junco]

Thanks!

[ancient plank]

Question:

how would I go about proving for all natural numbers that pr = qr iff p = q, r > 0?
I'm trying to solve that question since quite a while now but just can't get it down.
I already proved that p + r = q + r iff p = q but the multiplication just doesn't make sense to me how to prove it.

I'll attach what I already have and the big gap is where I don't know how to progress (since idk how I'm supposed to derive that pk + p = qk + q iff pk = qk).

Any pointers or help would be appreciated.

[rugged moth]

first take r=1

[ancient plank]

why? I intentionally made it s(r) instead of r, so I can assume that I multiply by positive number and exclude 0 that way

[distant glacier]

Anybody really familiar with the Collatz Conjecture and think they could help me figure out if I've found a new pattern in the gaps between orbital lengths?

[torn escarp]

post it, maybe someone will read it and give you feedback

[distant glacier]

Thanks, wasn't sure if posting links was allowed. Here is a small writeup I posted on Reddit. https://www.reddit.com/r/Collatz/comments/rpfka9/interesting_fractallike_structure_found_within/

If it gains interest, I may do a video.

[oblique olive]

Yo is anyone taking math kangaroo

[ancient plank]

I start to think that there might not even be a need to prove this 🤔

Because if we consider. That *(x,y) is a function, then it will give the same output if it gets the same two arguments x and y.
Now if we consider p = q, then pr = qr has to hold true because I'm multiplying the same values with each other.

So on a basis of function theory, it has to be the same result.

Is that correct?

[torn escarp]

sounds wrong, I think you need to go back to what your axioms are

[ancient plank]

Peano

But idk how my axioms (or even the theorems i have proven) would help in this case

[wooden glen]

"p = q implies pr=qr" is just the substitution property of equals. The other direction requires more finesse.

Have you proved trichotomy (x=y or x<y or x>y)?

[ancient plank]

Oh so basically the point that I brought up only works for "if p=q then pr had to be =qr" but not reverse

[ancient plank]

No I haven't

[wooden glen]

The way I can see would require that (and then prove "p<q and r != 0 implies pr<qr" by induction on r).

[ancient plank]

1. i dont really have a clue how i would prove it for pr<qr if p<r
2. how would that help me for the actual theorem?

[wooden glen]

2. Prove the contrapositive: "if p != q then pr != qr" Split into cases according to whether p<q or p>q.

1. The r=0 case is vacuous. The r=1 case is trivial.

For the general induction step you know that p<q and pr<qr and must prove that p(r+1)<q(r+1) ...

[wooden crater]

here is how i would argue: ||pr = qr <==> pr - qr = 0 <==> r(p - q) = 0 <==> r = 0 or p - q = 0||

[wooden glen]

He said Peano axioms, so I don't think he has all of Z to work in.

[sacred junco]

Divide by r pr=qr so p=q

[wooden crater]

some peano axioms start with 0 being a natural number, didnt see whether or not they specified

[wooden crater]

and it looks like they are using zero in this image

[wooden glen]

That doesn't help here, you need negative numbers for the reasoning using subtraction to work.

[wooden crater]

not necessarily

just define p - q to be the right positive number if p > q and 0 otherwise. you could still arrive at the same result with some additional steps

[wooden glen]

With that kind of subtraction, pr = qr is not equivalent to pr - qr = 0.

And even more importantly, p-q=0 does not imply p=q.

[empty owl]

||Noting that the successor function is r(h), given that p<q and pr<qr, we have pr<qr <=> pr+p<qr+p <=> p(r+1)<qr+p also pr<qr <=> pr+q<qr+q <=> pr+q<q(r+1). Claim: pr+p<pr+q<qr+p<qr+q <=> (pr)+q<(qr)+p <=> (p+ph)+q<(q+qh)+p <=> ph+(p+q)<qh+(p+q) <=> ph<qh, therefore it is the case that pr+p<pr+q<qr+p<qr+q <=> pr+p<qr+q <=> p(r+1)<q(r+1). ||

Proof for p<q by induction on r, i think someone mentioned the r=1 case is trivial.

[wooden crater]

yes but you can get p - q <= 0 and q - p <= 0

[empty owl]

Under these axioms, -1 isn't included in the set since 0 is the smallest integer (0 is also treated as an integer in this case). So p-q=p+(-1)q wouldn't be possible.

To be more general, there does not exist an integer, say p, such that p<0.

[wooden crater]

okay, maybe that was a bit misleading. but referring to this, you can get p <= q and q <= p

[sudden swift]

if you're taking the arithmetic derivative of a limit, can you switch them to be the limit of the arithmetic derivative

it seems like you should be able to but I don't know how I'd prove it at all

[empty owl]

I'm thinking that algebraic laws of limits still apply.

[north garnet]

Hey, does this seem correct to anyone?

<@&286206848099549185>

[empty owl]

The sum of 3 squares is (a^2)+(b^2)+(c^2)

[quick furnace]

parentheses unnecessary

[north garnet]

I specified that a b and c were square numbers in the assumption. The exponent is not necessary to the calculation as far as I can tell.

One of the issues is that I can condense the cases.

I think, anyway.

[wooden glen]

Wait, how were those 10 particular cases chosen?

[north garnet]

The only numbers mod 5 are 0, 1, 2, 3, 4. If you square these, then your only options mod 5 are 0, 1, 4

Since we need 3 numbers, it's just every combination of these 3

[wooden glen]

There should be 27 combinations possible and you're only listing 10 of them. How did you choose which 10 deserve consideration?

[north garnet]

Oof, I just missed the other cases then

Well, I didn't include any repeat cases

so that's probably part of it

[wooden glen]

I'm just confused because your list seems to completely random.

[north garnet]

How so?

[wooden glen]

If there is a system to how you constructed it, I don't see what it is.

[north garnet]

No system, it's just possible combinations of the 3 squared numbers mod 5.

[wooden glen]

Hmm, it looks like you're only showing sums where the three terms are in non-decreasing order.

[north garnet]

Just to show that in order to be equivalent to 0 mod 5, 0 is a necessary part of the combination. Per the problem statement.

[wooden glen]

But I cannot discern any rhyme or reason to the sequence you're listing those choices in.

[north garnet]

There isn't any. The only requirment is that they be combinations of 0, 1 ,4. Other than that, it's essentially random.

In an attempt to find every possible combinations.

[wooden glen]

Are you deliberately randomizing the order?

Why?

[north garnet]

Nope

I just typed them out as I came up with them

[wooden glen]

To make it more difficult for the reader to convince himself that you have all of the possibilities?

[north garnet]

No, this isn't for an assignment or anything, so I just did it informally.

I wasn't considering the reader, I suppose. Hence the "stream of consciousness".

[wooden glen]

By the way, a quicker argument than listing all possibilities (and risk missing something) would be: Instead of writing the squares as 0, 1, and 4, write the squares as 0, 1, and -1 modulo 5. Now the sum of three of those without taking mod 5 afterwards is somewhere between -3 and 3. The only number in that range that is divisible by 5 is 0. However, if a sum of 3 numbers is 0, they can't all be odd, so at least one of the reduced squares has to be even, for which the only possibility is 0.

[north garnet]

Hm, I didn't know zero was considered even.

[wooden glen]

Zero is 2 times something, namely 2­·0, so it is even.

[north garnet]

This is a nice argument, though. I knew there must be a simpler way to do it.

Ok, I see.

Thanks for the insight

[empty owl]

I have a problem with over emphasizing things :/

[north garnet]

Are there any theorems that state that the power of an integer n, is always zero mod n?

[inner anchor]

A number is zero mod n if and only if it is divisible by n

Now n^k = n * n^(k-1) which implies that n^k is divisible by n when k > 0

[north garnet]

Alright, cool. Thanks 🙂

[north garnet]

If something is true in mod 26, Is it also true in mod 2 or 13?

[inner crest]

yes 26q+r=2(13q)+r

@north garnet

[north garnet]

Alright, cool. Thanks 👌

[wanton torrent]

Hey, what does it mean 1 mod 3?

I mean, $S = { \pm 1 ($mod $3)}$ is a generator of $\mathbb{Z}/3\mathbb{Z}$

[sterile pumice]

mns

[wanton torrent]

but

how so? like every element of {0,1,2} can be obtained by $1 \equiv b$ mod (3) for some $b \in Z$ ?

[sterile pumice]

mns

[stiff rivet]

every element is a finite sum of generators

[rain mountain]

2+totient(1000) right lol

[torn escarp]

that's an upper bound, you need to show that it's the minimum, depends on what the order of 1978 is

and that'd be if gcd(1978, 1000)=1 but clearly they're both even so that can't work

[sterile pumice]

centuryegg

[supple timber]

[supple timber]

Can anyone give me a hint about this problem? I'm struggling a lot.Given a number X, change the order of his digits(permutation of its digits) to obtain a new number Y which has all only has the digits from X, knowing that |(X-Y)| =391738A .where A might be any digit from 0 to 9.I tried to classify every digits as coefficient of this: $ax10^6+bx10^5...+fx10+g$ but i'm stucked trying to find a relationship from the coefficients of X and Y

[sterile pumice]

centuryegg

[bleak igloo]

Here, i'm doiing the RREF of this matrix and getting as the result of the right side, 4 4, but the answer is 3 3. Can someone help me ?

[torn escarp]

show your work and I'll point out where you go wrong

[bleak igloo]

i was doing with the wrong equation, but now i got 3/5 i'll send a photo of it

[torn escarp]

ok 👍

[bleak igloo]

it's not RREF since i dk if i can divide by four the last row

[torn escarp]

in your first step you do R_2 - 3R_1 but that should only change the second row, not the first

I don't follow how you're working it

[bleak igloo]

i wrote it wrong should've be R1-3r2

[torn escarp]

then you flipped them it looks like

[bleak igloo]

yeah

[torn escarp]

ok that's fine then

next you subtract makes sense

4 has an inverse, you can find it either by trial and error, bezout's theorem, or fermat's little theorem

basically you just need to find something that multiplies by 4 that has remainder 1 when divided by 7

there aren't that many cases to check, I'd just start going in order and multiply 4 by 2, then if htat doesn't work by 3, etc

[bleak igloo]

ok , I'll try here

thankkss

[torn escarp]

yeah you're welcome

[bleak igloo]

multiplying by two i got the answet

thanks

[torn escarp]

yup, that's it

[bleak igloo]

i can't divide by four cause i would get 5/4 and that isn't allowed in this set , right ?

since it only accept integers

[torn escarp]

well it's fine, it's just 4^-1 = 2 here

people usually like to keep them all to within the set of representatives {0,1,2,3,4,5,6}