elementary-number-theory

[halcyon osprey]

Suppose we had a lemma that said whenever a|e and b|e and e|ab, then ab/e | gcd(a,b).

Do you see how we could use this to prove the statement?

[modern canyon]

No, they're used all the time almost everywhere in maths. We used them since high school..
When someone does not know their meaning, these advanced university-level channels are certainly probably not for them.

[long lion]

bruh

i'd agree with the opinions of the ppl above here

ofc if u use them ppl will understand what they are

but a lot of ppl seem to forget that if u write a proof words would be useful lol

[modern canyon]

Proofs are polluted by too many words in natural language. Sure, it is a choice of style, but mathematicians must understand such basic formal language.

[torn escarp]

wrong

[modern canyon]

Definitely not.

[modern canyon]

First I mistook this for an advanced channel

[long lion]

Proofs are polluted by too many words in natural language
surely this is not serious lol

[torn escarp]

[modern canyon]

It is obviously both serious and true. But nvm, I didn't mean to talk to students about this.

[long lion]

me when my proofs look like this

[modern canyon]

Misses the point. You could still structure that nicely.

This is an example of good proof structure.

[halcyon osprey]

Of course I know what they mean; at the same time I very rarely see them in textbooks or papers, and I think that’s for a reason. Keeping in the words “or” and “and” make things easier to parse for most people, and prevent overloading of notation in contexts like diff geo or top, where the symbols can mean wedge

[runic token]

this has to be satire

i genuinely cannot comprehend this not being a joke

[modern canyon]

I guess you would prefer to fill multiple pages with dense text instead? Disgusting.

[runic token]

yes i would good lord

[worn ledge]

You do realize that symbols are shorthand for words, you can write down a proof practically only using words

[modern canyon]

Of course, to make it entirely ugly, overbloated, unreadable, and harder to validate.

[runic token]

???????

[distant cairn]

Unreadable 🔥

[runic token]

proofs are about communication

[manic arch]

this is prob readable if you know full well what each of these symbols mean, now imagine having to introduce another reader to whatever you are doing

this is why math literature is written in English

[runic token]

an alien writing things down in a box does not mathematics make

[worn ledge]

There should be proper grammar in a proof just like a text

So it’s not overbloated or unreadable if you take the time to write it nicely, after all we’re humans

[low oasis]

bait used to be believable

[modern canyon]

You guys should realize that social proofs are not formal proofs (see this introduction), and they come in many shades, from purely natural language proofs to formal proofs.

[forest plank]

!show

[rotund gust]

Show your work, and if possible, explain where you are stuck.

[runic token]

im gonna start tweaking

[low oasis]

don't tell me how to do my job

[runic token]

whoa

wew

i haven't seen you in forever

[manic arch]

what you posted seems like neither lol

[low oasis]

a proof is something that convinces my supervisor to stfu

[runic token]

weren't you a cringe mod for a little bit or something

[low oasis]

valley have you just been in a time capsule for like a year

[worn ledge]

Mathematics is a social activity lmao

[manic arch]

not human-readable and not a program that a proof-checker can read, what's the point then

[runic token]

idk

have i seen you?? am i crazy

[modern canyon]

Don't make false claims about what I did.

[runic token]

look it's not me

it's just been forever frfr

[distant cairn]

Do you think Principia Mathematica is too much language @modern canyon

[manic arch]

assuming the convo started from this, I agree that mixing up logic symbols for their literal meaning in English is kind of silly and hurts human-readability

silly, because they're defined as an operator in first order logic not as shorthands for phrases like this

[runic token]

if this is a troll they're the best troll since like, the balloon capacitator guy

and this is really funny

[modern canyon]

You told me

Mathematics is a social activity lmao
after I used the term
social proofs
for the usual way in which proofs are written.
Do you see your error?

[runic token]

but if this isnt a troll idk what to think

[low oasis]

you come here and start yapping about how every professional mathematician since at least Newton have been writing proofs wrong

scratch that, since Archimedes

[manic arch]

idt it's a troll just kind of pedantic about the wrong things altogether

I'm off this convo lol

[runic token]

bye deri!

[worn ledge]

Are you a robot?

[modern canyon]

I'm not trolling, you just suck at interpreting my words correctly.

[runic token]

u said this?

lord

[halcyon osprey]

Maybe try giving it to us in symbols then, big dawg

[modern canyon]

Natural language sucks, the issue is, most humans suck even more at formal language.

Question is what the research is for - humans or automation.

[torn escarp]

therefore we should use the word "and" instead of a symbol for it, right?

[worn ledge]

Natural language is beautiful

[halcyon osprey]

When I write a “proof” in a paper, my goal is not to give a completely rigorous argument. My goal is to invoke in the reader’s mind the right ideas to allow them to construct a completely rigorous argument, should they do choose

[modern canyon]

Definitely not. I do not want such ignorant people to believe they understand anything about my proofs.

[halcyon osprey]

Fuck he was trolling

I got baited gg

[torn escarp]

I wish

[modern canyon]

Strongly disagree, but that's just a matter of taste 🤷

[worn ledge]

So you do have emotions!

[still flare]

Move on <3

[low oasis]

move IN

[random sand]

The former

[modern canyon]

You sure? To taste or to disagree are not emotions. 😄

[worn ledge]

Oh so you’re admitting to be a robot then?

[modern canyon]

Nah, I'm concealing.

Are cute little dragons robots?

[worn ledge]

This essay by Bill Thurston might be of interest to you https://arxiv.org/pdf/math/9404236

[modern canyon]

Wrong, this kind of stuff is what I care about the least when it comes to mathematics. I'm not that interested in culture and history.

[torn escarp]

can you all continue this in #math-pedagogy or somewhere else pretty please

[maiden depot]

relevant: https://jmlr.csail.mit.edu/reviewing-papers/knuth_mathematical_writing.pdf

[runic token]

what's y'all's favorite cute number theory problem that looks difficult but is easily solvable w basic tricks

good to know! i'll be sure to give it to the baby freshmen to play around with!

actually might do this

that sounds really funny

[modern canyon]

The things in between ⟦ and ⟧ are literally formulas (the first being an axiom of a deontic logic system). I gave that as an example because it is impossible to give a good proof there in only natual language, and those that mainly use words just bloat it up unnecessarily.
The formal symbols used outside of ⟦ ... ⟧ are pretty basic — a good high-school student should already know all of them, at least we did here.

[sudden swift]

it's not about knowing them it's about being able to actually understand what is going on

sure if someone spends like an hour working through the symbols they might get it

but like

they probably just won't

and if they actually need to check it then it's a nightmare

unnecessarily

[modern canyon]

The proof structure is X <=> (A => B), and A => ... => B. There is nothing hard about this.

[sudden swift]

there are literally nested brackets that begin and end on different lines

[modern canyon]

Just like in every simple program in almost every programming language. Still nothing hard about this.

[sudden swift]

I'm not reading a program I'm reading a piece of text trying to communicate a proof.

[modern canyon]

But it gets messy when not using indentation properly.

[sudden swift]

this is not effective communication

[modern canyon]

Misses the point. It's not about what you read, it is about that there is nothing hard about this.

[modern canyon]

yes it is

[sudden swift]

says who

[modern canyon]

It's true w.r.t. common definitions of "effective communication", who says or believes it or otherwise doesn't matter.

[sudden swift]

what?

[modern canyon]

But part of this is "complete and concise".

[sudden swift]

do you hear yourself?

[quaint gate]

we should listen to merosity chat

[sudden swift]

or read yourself i guess

[modern canyon]

Which makes using many words instead it not to be effective communication.

[sudden swift]

if nobody can read it it's not effective

at least 3 mathematicians here have said explicitly that it's difficult to parse

[modern canyon]

Many people can read this. And of course it is not effective for those who hate formal language. But idgaf about those.

BTW, all programming languages are also fully formalized.

[sudden swift]

good luck in your academic career then

[modern canyon]

And many people love to code.

[modern canyon]

I would rather kms than having to deal with people professionally who hate formal language.

[quaint gate]

if you have ||prime factorization|| at hand then this becomes much straightforward btw

[torn escarp]

https://tenor.com/view/anjo-anjinho-angel-smile-bee-gif-15404279

[tranquil nacelle]

@everyone Find a formula that describes all fractions that kiss 13/31 and
are less than 13/31.
Repeat for all fractions that kiss 13/31 and are greater than 13/31.
Hint: How would you tell if one fraction is bigger than another?

i found the diophantine equation

31x - 13y = 1

and i got (-5-13n)/(-12-31n)

[dusky aspen]

Yet to prove that

[tranquil nacelle]

which represents all kissing fractions

but how do you find the fractions less than 13/31 and greater than 13/31 but still kissing???

[torn escarp]

whats... kissing... 😳

[runic token]

trying to ping 200k ppl for that is crazy work btw

[dusky aspen]

https://tenor.com/view/everyone-gif-20796674

[tranquil nacelle]

ad-bc = 1

[tranquil nacelle]

ok

[torn escarp]

and that's for fractions a/b and c/d I'm guessing?

[coral merlin]

is finding (a method to calculate) 2¹⁰⁰ #elementary-number-theory ?

maybe it is

So I counted at least 3-digit 4×32 (number of rules of my yellow pad paper) powers of 2

and I'm noticing a pattern

for ones digit it's simple: it cycles from 1, 4, 8, to 6.

For tens digit, it cycles every 20 numbers

For hundreds digit, it's every 68

But

in actuality, the cycle of the next digit begins after every 5 cycles of the previous digit

with an offset of 3 numbers

I've only done it to first 3 digits. Idk if the pattern continues to >3 digits

It could continue exponentially, I'm not sure

[forest plank]

Well you can try to prove that there is always a cycle 😊😊😊

You are now almost like the greatest number theorists in history (Fermat, euler, gauss). First, did a lot of calculations and noticed some pattern. Then, proved this pattern.

You are 50% there 😊

[coral merlin]

oh I see

interesting

btw it started here #odes-and-pdes message

[coral merlin]

i thought you're Merosity

imma continue this later

[coral merlin]

i think i miscounted this

it's actually 100, not 68

now the pattern looks more obvious

4×5=20

20×5=100

would the thousands digit pattern cycle every 400 numbers?

[forest plank]

https://www.exploringbinary.com/patterns-in-the-last-digits-of-the-positive-powers-of-two/

[coral merlin]

ohhh that's nice

I've been thinking when does the next digit start

now i see

wait idk

I'll just read it first

oh man i mistakenly said 400

should be 500

bc the pattern is u multiply it by 5

i switched up 4 and 5

[halcyon osprey]

I vaguely remember something from number theory that this is a corollary of

Some lifting lemma we used to prove Z/qZ for odd prime power q has cyclic unit group

I should go look back at that

@coral merlin It’s definitely a useful exercise though to try and prove that the periods of the cycles are at most 4•5^(n-1)

I’m happy to give small hints towards that if you are interested and stuck

[tender scaffold]

if n is a Lucas pseudoprime for some (P,Q), is it a Fermat pseudoprime for some base b ?

[dusky aspen]

prove that $ \exists \alpha, \beta : a\alpha + b \beta =1 $, then $gcd(a,b)=1$

[sterile pumice]

Mr bean is not $\R \setminus \Q$

[dusky aspen]

Any hints chat?

[quaint gate]

d=gcd(a,b) divides both a and b

[dusky aspen]

yeah, sure

I'm trying to use WOP

trying to think of a set that will work

[quaint gate]

Good luck.

[dusky aspen]

wdym?

oh yeah, I need it, I suck at ENT

So I thus have to find $\gcd(a, \frac{1-b \beta}{\alpha})$

[sterile pumice]

Mr bean is not $\R \setminus \Q$

[quaint gate]

Your question isnt even very well formed tbh

i take it you mean if there are integrrs alpha, beta s.t. a.alpha +b.beta=1 then gcd(a,b)=1

simply write down what it means for d=gcd(a,b) to divide a and divide b and maybe substitute stuff into the given equation

[dusky aspen]

Ok, let me post the entire question, I just posted the direction I wanted to prove

prove that $\gcd(a,b) =1 $ iff \exists \alpha, \btea \in\Z : a \alpha + b \beta =1$

$\gcd(a,b) =1 $ iff \exists \alpha, \btea \in\Z : a \alpha + b \beta =1$

$\gcd(a,b) =1$ iff $\exists \alpha, \beta \in\Z : a \alpha + b \beta =1$

[sterile pumice]

Mr bean is not $\R \setminus \Q$

[dusky aspen]

I'm trying to show $\exists \alpha, \beta \in \Z $ such that if $a \alpha + b \beta =1 \implies \gcd(a,b)=1$

[sterile pumice]

Mr bean is not $\R \setminus \Q$

[dusky aspen]

for the other direction is trivial

so I want to show that $\gcd(a, \frac{1- a \alpha}{\beta})=1$

[quaint gate]

no, youre trying to show: if there are integers alpha and beta such that a.alpha+b.beta =1 then gcd(a,b) is 1.

whT is the gcd of a and a?

[dusky aspen]

a

[quaint gate]

what if a is negative or 0?

[dusky aspen]

||a|

[quaint gate]

yeah, the book i used defined gcd of 0,0 to be 0

So is it 1?

[quaint gate]

how did you even get to this?

[dusky aspen]

oops

[sterile pumice]

Mr bean is not $\R \setminus \Q$

[quaint gate]

the idea is that if d=gcd(a,b) divides both a and b then it divides anything of the form au+bv so it divides the thing on the left of your given eqn, so it divides the thing on the right

1 is on the right. What does it mean to divide 1

[dusky aspen]

a,b are co-prime

[quaint gate]

1=xy, x,y are integers. what can you say about x?

[dusky aspen]

x=1 or -1

[quaint gate]

yeah

this is pretty much the idea of the proof

[dusky aspen]

hmm

[quaint gate]

how is the other direction trivial btw?

[dusky aspen]

It follows form bezouts lemma

I can use that as I prove that earlier

[quaint gate]

did you use the wop for that?

[dusky aspen]

yes

[quaint gate]

okay

[dusky aspen]

I've previously proven that $\gcd(a,1-a)=1$. Form which it follows that $\gcd(a,1- \alpha a)=1$

[sterile pumice]

Mr bean is not $\R \setminus \Q$

[dusky aspen]

I don;t see how this helps

[quaint gate]

a= ud, b=vd substitute that into a.alpha+b.beta=1

[dusky aspen]

$u\alpha d + v \alpha d =1$

[sterile pumice]

Mr bean is not $\R \setminus \Q$

[dusky aspen]

oh

okay

that was trivial

shit

thanks

so $a=k_1a; b= k_2a$, from which $a \mid b$ follows

[sterile pumice]

Mr bean is not $\R \setminus \Q$

[dusky aspen]

if $ a \mid b \implies b=ak_1$. But we also know the largest integer that divides $a$ is $a$ itself. and that $a \mid b$. so it follows that gcd(a,b)=a

[sterile pumice]

Mr bean is not $\R \setminus \Q$

[dusky aspen]

is this fine?

[ivory cosmos]

hi, everyone is a factor of 0 because 0 = k * 0 right

by book says 0 is the only factor of 0

this is wrong right?

[patent acorn]

yep

[ivory cosmos]

or are there multiple definitions?

[ivory cosmos]

but this is from the handbook of a standardized exam

[patent acorn]

0 is the only multiple of 0 and that might be what the book was going for, but yeah i don't think there's a reasonable definition of "factor" by which 0's factors aren't just "everything"

[ivory cosmos]

wait is it possible that they’re defining their own definition here?

[patent acorn]

i mean tbh at this point i expect standardised exams to make less mathematical sense than most texts about mathematics

[patent acorn]

yeah i think the most reasonable way to interpret this is that their definition is just like, "a is a factor of b if b = a * n for some nonzero n" or something

[ivory cosmos]

for completion sake

[ivory cosmos]

oh

[patent acorn]

oh ok no that makes sense actually and you just read it wrong

[ivory cosmos]

but then how do they say 0 is a factor of 0

[ivory cosmos]

oh

[patent acorn]

"0 is not a factor of any integer except 0"

so this means that like, 0 isn't a factor of 5, which makes sense, there's no number that you can multiply 0 by to get 5

[ivory cosmos]

oh

[patent acorn]

the part of this statement that's about the factors of 0 is "0 is a multiple of every integer" which is the same as "the factors of 0 are every integer"

[ivory cosmos]

i’m blind

someone quoted this and said “only factor of 0 is 0”

they’re wrong right?

[patent acorn]

yes

[ivory cosmos]

thanks

i wish there was a reading channel too

[little ferry]

(aimed at high schoolers btw)

[lethal cedar]

I just wanted to check, but in the world of say mod 3, 3 and 6 would be considered the "same" right? like in the reals we never say 3 = 6, but in mod 3, 3 = 6 makes sense?

[torn escarp]

you can say they are in the same equivalence class

so now the question is, what's the equivalence relation?

[runic token]

<@&268886789983436800> just in the unlikely case this is some weird scam server

[cinder linden]

don’t advertise your server here

[little ferry]

💀

it's a nonprofit, not a scam, but okay

[lethal cedar]

right right i see thanks

also what does incongruent solutions mean

[uneven shoal]

hey i was just thinking about this, i know theres a bunch of weird names for types of numbers, so is there a name for a number n such that gcd(m,n) = 1 if and only if m is prime?

[still flare]

Well n cannot be composite (and >1), since any prime factor p of n will have gcd(p, n) =/= 1.
So suppose n is prime. But then gcd(n, n) = n =/= 1.
So the only possibility left is n=1, and gcd(m, 1) = 1 always.

So there exists no such number n.

[bold badge]

Yeah

And even if you made m and n distinct it can’t work cause you get gcd(m,n) =/= 1 whenever m is a multiple of n

[torn escarp]

what makes you think about that

[magic drum]

Could anyone hint me what to do for this? Im pretty sure i have to show that (c/p)=1

[uneven shoal]

the groups U_n that contain only primes

like U_12

[uneven shoal]

i made a mistake it shouldnt be iff just if

[forest plank]

In the top you actually have Jacobi symbol, not legendre symbol 🤔 because a may be not prime.. but everything still holds, ok

[forest plank]

Ok I think I did it lol

Since (a/p) = 1 then there is some d such that a= d^2

We have a^2 + b^2 = 0 (mod p)

d^4 = -b^2

Then d^2 = ib (where i is some sqrt(-1) mod p)

Then

1 = (ib/p) = (i/p)(b/p)

By euler criterion (i/p) = i ^(p-1/2) = i ^(p-1/4)(2) = (-1)^(p-1/4)

So (b/p) = (-1)^(p-1/4)

[still flare]

The name for such a number is 1.

[charred roost]

So the numbers n such that 1 < k < n and gcd(k, n) = 1 implies k is prime? Not sure if they have a name, but it seems n must be highly composite, atleast for large n. The first such numbers are 3, 4, 6, 8, 12, unless I'm mistaken

https://oeis.org/search?q=3%2C4%2C6%2C8%2C12%2C18%2C24&language=english&go=Search
could be one of these sequences

[patent acorn]

yeah it's https://oeis.org/A048597

1, 2, 3, 4, 6, 8, 12, 18, 24, 30 is all of them apparently

...it makes sense that there'd be finitely many because there's just too many primes

if p^2 < n then p^2 can't be coprime to n so p divides n

which means that for numbers above 25 they all have to be multiples of 2*3*5 = 30

so the next number you'd try is 60 but that's > 49 so it has to be a multiple of 7 as well, 30*7 = 210

so you jump to 210 but now that covers 11 and 13 so it has to be a multiple of 30030

there's enough primes that you're never going to "catch up" with this process, it will just keep getting bigger and bigger

[patent acorn]

in fact this condition is equivalent
if you consider any k then you can take its smallest prime factor p, and either that is k (we're done), or k is p * m for some m > p (because otherwise the smallest prime factor of m is smaller than p), which means p^2 is also < n

[light prawn]

Find all positive integers k for which there exists a positive integer m such that k!+48=48(k+1)^m

[forest plank]

!show

[rotund gust]

Show your work, and if possible, explain where you are stuck.

[cunning stream]

Find the least nonnegative solutions of 2x+3y \equiv 4 (mod 7). I don't understand the question, if there was only one variable x then I can find the least solution x

[ivory cosmos]

least non negative?

yeah it doesn’t make sense to me either but i don’t know much number theory

[patent acorn]

i mean i guess you can just say like, (2,0) and (2,7) are both nonnegative solutions but (2,7) isn't a least one because (2,0) is strictly smaller than it
but (2,0) and (0,6) aren't comparable so they can both be minimal

[light prawn]

Find all primes such that there exists positive integer m such that:
2(p-3)!+1=p^m

the (p-3)! being present makes me want to use wilson's thm

however it doesn't work

lte is too much of a curveball

[long lion]

ok this is very much a sketch of an idea

but rearrange to get

2(p-3)! = p^m - 1

then take v_2 of both sides

LHS is ~linear

m is even for p large enough

so RHS is v(p-1)+v(p+1) - 1 + v(m)

note v(p-1) and v(p+1) are <= O(log(p))

so v(m) ~ linear - log ~ linear

so m ~ kp for p large enough

then you get a contradiction with size

that's a very unrigorous sketch of a proof, but tbh it's not the cealnest

potentially someone might have a better proof

[light prawn]

you gotta work with what you have ig

[bold badge]

Real idk why they hating

[torn escarp]

unfortunately all Wilson's theorem says is when we reduce this mod p that it's true, since m is positive and -1 = (p-1)! = 2(p-3)! mod p

[light prawn]

I also reached the same conclusion, #elementary-number-theory message

[paper dawn]

hey, so I am trying to prove the following:
Except I am stuck. I don't even know if the stuff I did is right.

here's the theorem. I used btw

oops I might have had the solution all this time but thought it was too trivial

I believe this is right

[forest plank]

This "exercise" is often used to prove the theorem.. so potentially might be a circular proof...

[lethal cedar]

for the second problem, why is it valid to work with modulo 25

instead of modulo 100

oh is it just chinese remainder theorem

wait actually no i dont understand it

[long lion]

yes

work mod 4 and mod 25 instead of mod 100

[noble obsidian]

I am TAing for this course and a student was talking about the sequence of primes p_{2^m} for m in N. Does anyone know if this was studied?

[torn escarp]

for all m there exists at least one prime between the m and m+1 term...

sorry not that I'm aware, you could try plugging it into OEIS and see what pops out though, that's as good as it'll probably get

[noble obsidian]

okay. Yeah I presume it would be really difficult

[torn escarp]

I don't know what's difficult about it, what's interesting about it?

[noble obsidian]

Oh just showing that limsup(p_n - p_(n-1) ) = infty by looking at this subsequence

[magic drum]

$(x^2-1)(x^2-2^2)....(x^2-18^2)=x^{36}+a_1x^{34}+...+a_{17}x+a_{18}.$

Show that $a_i \equiv 0 \pmod {37}$ for $1\le i\le 17$

[sterile pumice]

somethingwrong

[magic drum]

Any clues on what to do with this? I know that it having 1,2,3,..36 modulo 37 as roots might help but Idk what to do from here

[long lion]

hint: ||x^36 - 1 also has the exact same roots||

(note you do have to be careful since ||0 also has (almost) the same roots||)

[coral nacelle]

I think using
m<p
--> v2(m) < log2(p)
Then v of RHS is all log and LHS is linear so yes there is a contradiction with size
What is the source of the problem btw

[sacred junco]

hello!

im

[stuck token]

LOL

if I'm sorting a range of integers so that they descend by the number of 0s in their binary representations, why might it produce sets in a 6,15,20 pattern (i.e. always return triangular numbers)

this might make 0 sense I have visuals if necessary

[dapper hound]

help

[torn escarp]

this isn't number theory, check out #❓how-to-get-help to make a question channel for help, good luck

[sterile pumice]

NicknamedTwice

[fallen cypress]

i want to code golf this, but my C program is too slow:

#include <stdio.h>

int last(unsigned long long n) {
    if (n < 10) return (int[]){1, 1, 2, 6, 4, 2, 2, 4, 2, 8}[n];
    int cycle[] = {6, 2, 4, 8};
    int result = last(n / 5) * cycle[n % 4] % 10;
    for (unsigned long long i = n / 5; i > 0; i /= 5)
        res = res * 6 % 10;
    return res;
}

int main() {
    unsigned long long n;
    scanf("%llu", &n);
    printf("%d\n", last(n));
    return 0;
}

[torn escarp]

there are more powers of 2 than powers of 5 in N!, so the power of 10 dividing N! is the same as the power of 5 dividing N!.

A trick for finding the power of $5$ dividing $N!$ is called Legendre's theorem, $$v_5(N!) = \frac{N-s_5(N)}{4}$$ where $v_5(x)$ is the power of $5$ dividing $x$ and $s_5(x)$ is the sum of digits of $x$ in base $5$.

[sterile pumice]

Merosity

[torn escarp]

getting the sum of digits in base 5 shouldn't be too hard, just c += N % 5 and N/=5 to pull the digits off one at a time

[fallen cypress]

i see thanks

[torn escarp]

yeah let me know how that goes

[fallen cypress]

it was midnight for me and now i have to go to school

but i'll code it up when i reach back home

[fallen cypress]

that theorem was still too slow and didnt work for really big numbers

i found another method to do it though and it works with inputs up to 10^19

const int a[] = { 1, 1, 2, 1, 4 };

int f(int k, unsigned long long x) {
    int r = x < 5 ? 3 : f(k + 1, x / 5);
    int d = x % 5;
    return d ? r * a[d] * (1 << (d * k % 4)) % 5 : r;
}
``` i used this to help https://www.mathpages.com/home/kmath489.htm

[torn escarp]

how´d you implement it? I just ran it myself and was almost instantaneous

doing it computes it for 10^10000 in 39 ms

for me at least

but I implemented it in pari-gp as this one-liner

f(N) = m=N; s=0; while(N>0, s+= N%5; N=floor(N/5)); return((m-s)/4);

[silver oak]

that's some kind of insanity

[torn escarp]

https://tenor.com/view/cat-insane-gif-21702784

[silver oak]

you just divide by 5 and add, it's maybe only twice as fast but you look sane

f(N) = s=0; while(N>0, N=floor(N/5); s+= N); return s;
``` so like this or something

[torn escarp]

idk I'm distracted at the moment but I don't think that'll return the same thing

I guess maybe you're doing the N-s_5(N) all at once with that, or that's the intent?

[silver oak]

i'm not trying to optimize yours, idk how it works

[torn escarp]

oh most of that is just getting the sum of digits in base 5

[silver oak]

yes but i don't know why it works

[torn escarp]

so you need the s+=N%5 step since that gets the remainder when divided by 5 of N

[silver oak]

it's just unnecessry complicating

[torn escarp]

is it?

generically speaking $n=n_0+n_1b+n_2b^2 + n_3b^3 + \cdots$ is the base b expansion of $n$. Hopefully clear that we can get the first digits by looking at the remainder when divided by b

[sterile pumice]

Merosity

[torn escarp]

then floor(n/b) throws that digit away and moves the next one up and repeats the process

until eventually hitting 0

maybe there's a more efficient way of doing this you have in mind that I don't understand

[silver oak]

we are both looking for the amount of trailing zeroes in the decimal expansion, or the power of 5

[torn escarp]

no

I'm looking for the sum of digits of N in base 5

$$v_p(n!) = \frac{n-s_p(n)}{p-1}$$

[sterile pumice]

Merosity

[torn escarp]

the left side yes, that's ultimately what we want, but via the formula on the right

[silver oak]

yes, like i ran your thing, it says F(72838) = 18205

[torn escarp]

oh ok, that's good

[silver oak]

the idea is that you count multiples of 5 in 1..N, then count multiples of 25 then count multiples of 125...

and all the double counting matches what we want

[torn escarp]

[torn escarp]

I feel like we're back to here again idk what I can tell you right now

[silver oak]

it's not more efficient clearly, because divmod is a thing, you can find remainder and quotient in the same time as just one of them (idk maybe)

just far less complicated

i don't know how to solve the original problem from here, that's the interesting part

yeah, it was pointless ok

[torn escarp]

I'm just busy so idk how your thing works yet

us has some kind of gender reveal party going on rn

[silver oak]

neither of our things helps the problem

[torn escarp]

mine solves it

as far as I'm aware

[silver oak]

idk why you think that

[torn escarp]

LOL you're right I just looked at the problem no idea what I'm doing

whack, I'm going to suspend my posting privileges of myself from this channel until I'm sober 🤣

[minor thicket]

Prepping for an exam tomorrow and I'm a bit stuck on this problem -- split it into two congruences (x^2 \equiv 1 mod p and x^2 equiv 1 mod 2p+1) and tried proceeding via CRT but got stuck. Is this the correct approach?

[forest plank]

Yes

[cunning stream]

what is the precise definition of a pseudoprime to the base a? Sometimes I saw a^n /equiv a (mod n), different sources wrote a^(n-1) /equiv a (mod n). For the first form I don't see they specify (a,n)=1 so that I can cancel a to bring the congruence to the second form

[fallen cypress]

pari/gp is meant to handle for way larger numbers than C can handle

i was limited by the 64-bit integer size in C but pari/gp's arbitrary precision arithmetic makes it better for handling huge numbers like 10^10000

[torn escarp]

I think that's besides the point, the algorithm I have is just completely wrong so doesn't matter how fast it is

[fallen cypress]

oh ok

[warm plume]

Hey, can sb please give an explanation to this: Determine all ordered pairs $(a,p)$ of positive integers, with $p$ prime, such that $p^a+a^4$ is a perfect square.

Proposed by Tahjib Hossain Khan, Bangladesh This is a recent IMO Shortlist Problem (I think 2023), the official solution uses a lot of case works. Maybe somebody can provide a nicer solution or could explain the motivation behind the case works. Thanks! Best Julius!

[sterile pumice]

Julius

[forest plank]

Bro is expecting us to solve a imo problem 😭😭💀💀

[fallen cypress]

is there a formula i could use if i wanted to find the sum of digits in n! instead?

is that even doable without storing the full number 🤔

or like how about the last k non-zero digits

should still be possible with modular arithmetic

[long lion]

i mean, ur effectively solving

$p^a + a^4 = x^2$

[sterile pumice]

LY

[long lion]

a^4 and x^2 are squares

so you can do a difference of 2 squares

$p^a = (x - a^2)(x+a^2)$

[sterile pumice]

LY

[long lion]

and then u can do stuff from there probably

i mean that gives you

$2a^2 = p^t + p^l$ where $t+l = a$

[sterile pumice]

LY

[long lion]

might be able to derive a contradiction with size or smth

yeah then you get

$a^2 \geq p^{a/2}$

[sterile pumice]

LY

[long lion]

if p = 2 you only need to check up until a=16

and then for p=3 a=7 is limit

p = 5 no sols

so only cases are p=2 and p=3

i suspect this'll be the official sol

lemme check

[long lion]

oh wait whoops messed this up

that's what i get for trying to solve it on discord lol

[long lion]

anyway yeah you look at p^t - p^l and then think abt what u can do with that

size is no longer something we can consider so try thinking about prime divisors instead

the official solutions with give like the best write-up but that's not necessarily how u should think about the problems

a lot of the times u just start by trying to do it and then it becomes clear u'll need to split into cases

[warm plume]

thanks!

[glass cosmos]

why is this part true

order(r) = n mod p^k

n | phi(p^k) = p^(k-1)(p-1)

I also agree

r^n = 1 mod p

so I thought we can conlcude is simply

order(r) mod p must divide n

and I mean I would also agree that

order(r) mod p must divide ph(p) = p-1

I just dont see how they have

(p-1) | n

n is a multiple of order (r)

unless order(r) mod p = p-1

is it simply the fact r !=1?

OHHH

I legit missed the first assumption

"choose a primitive root, r, of p"

order(r) = p-1 mod p

.close

[spark prawn]

i don't understand the reaons here

and this is under the condition of mod 5

[still flare]

Do you believe that 2^phi(5) = 1 mod 5?

Is that the issue you're having?

[spark prawn]

by phi(5) do you mean the totient of 5

[still flare]

Yes

The symbol for the totient function is the Greek letter phi.

[spark prawn]

i see

[spark prawn]

yeah i get this, but how is it related to the picture

[still flare]

Imagine we were looking at 2^400

Note that 400 = phi(5) * 100.

So what's 2^400 mod 5?

It's (2^phi(5))^100

Think about what this means and how you can use it in your question

[spark prawn]

oh so in this case we know 2^(151*phi(5))==2^phi(5) mod 5

oh i think i get it

so 2^606==2^(151*phi(5))*2^2= 4 mod 5

[icy trench]

Is solving Diphantine Equations in any way connected to other math fields or is it often (always) just for the sake of solving them? Or maybe applications in other sciences?

[sacred junco]

physics and chemistry

[icy trench]

And in other math fields?

[lunar moat]

Guys I was watching a lecture on p-adic numbers and there was a strange thing

Basically a guy made a series $9 + 9 * 10 + 9 * 10^2 + ...$
and said that this is an infinite geometric progression. And used a formula for infinite geometric progression to conclude that the sum is equal to $-1$, since $\frac{9}{1-10}=-\frac{9}{9}= -1$

[sterile pumice]

☀eek

[lunar moat]

Why the hell did he use it if the progression is non-decreasing?

And he also said that this makes sense since if we add +1 on both sides of $-1 = 9 + 9 * 10 + 9 * 10^2 + ...$ then the LHS is $0$ obviously and RHS is also 0 since we $9 + 1 = 10^1$ and then we pull 1 to the next summand, then $9 * 10 + 10 = 10^ 2$, and so on RHS becomes $0 + 0*10 + 0 10^2+010^3+...$

[sterile pumice]

☀eek

[lunar moat]

And since all coefficients are 0, LHS equals RHS

This is so wild. How is it even an argument and why does it align so well with the formula for geometric progression? Is this a coincidence or it is what people do in analytic number theory?

[patent acorn]

the progression doesn't have to be decreasing

this formula is valid as long as it converges

[lunar moat]

But the funny thing that it does not, but the guy lecturer says it's -1

[patent acorn]

well it does

...in the 10-adic numbers

[lunar moat]

It's mind blowing

Ok, so this all boils down to the way how we defined 10-adic numbers and it converges only in this narrow framework?

[sacred junco]

Nah

[patent acorn]

the fact that it diverges boils down to the way we defined the real numbers, and it diverges only in that narrow framework :)

but yeah basically, it converges in the 10-adic numbers and doesn't converge in the real numbers

or well, you don't actually have to skip all the way to the 10-adic numbers

[lunar moat]

Thank you, you clarified me this huge misunderstanding

[patent acorn]

you can look at this in the rationals and just use the 10-adic distance as your notion of "convergence"

[lunar moat]

What do you mean "look at this in the rationals"?

[patent acorn]

you can interpret this series in the rational numbers

and just, instead of the normal concept of distance between rational numbers where the distance between x and y is |x - y|

you use the 10-adic distance

then the series converges to -1

the main problem this has compared to using the 10-adic numbers directly, is that some sequences will sort of look like they "should" converge but don't actually have a rational number as their limit
the same way that the sequence 1, 1.4, 1.41, 1.414, 1.4142, ..., can't have as its limit (under the normal distance) "sqrt(2)" because that's not a rational number

[patent acorn]

the point here is that

a sequence x_n approaches a limit L if the values of x_n get arbitrarily close to L, right?

but that means you have to define what "close" means

[lunar moat]

yes

[patent acorn]

and stuff like "9 + 90 + 900 + 9000 + ... = -1" are just the result of a different notion of "closeness"

[lunar moat]

I mean we can define convergence without using distance functions right

Only using topology

[patent acorn]

well yes you can

that's just not really relevant in this case lol, given that both the normal Q/R and the p-adic numbers are metric spaces

[lunar moat]

Sorry, I don't know about p-adic distance so I did not fully understnad what you wrote

I will reread what you explained once I understand it

[torn escarp]

As far as the 10-adics go, it's probably best to define the 10-adic absolute value first. Then you can get your distance from that and use that to define your topology based on that metric.

for rational x, you define |x|_10 = 1/(largest power of 10 dividing x). So for an example, |20/17|_10 = 1/10

another thing you might want to see is what happens as n gets large here? |10^n|_10 -> 0

[torn escarp]

on the other hand, this sequence of rational numbers diverges because it 10^-n will become large 10-adically. This doesn't necessarily mean there isn't a sqrt(2) in the 10-adics, just that this sequence of rationals that converges in the reals doesn't converge to it. There are many algebraic numbers in the 10-adics, although they will usually not share the same sequences of rational numbers converging to them. That being said sqrt(2) isn't in the 10-adics, but there are others.

Of course that's not unique to irrational numbers, you've already seen -1 has a sequence of rationals that converge to it in the 10-adics and not in the reals. On the other hand .9, .99, .999, ... is a sequence of rationals that converges to 1 in R but diverges in Q_10 even though 1 is definitely in the 10-adics

[deep raptor]

Hello, in this video I Solve a number theory question using a system of congruence, and I wanted to share it. For those who watch it, I would appreciate some advice on how to improve my content. https://youtu.be/QPAqng3HGKs?si=Y7ZmqhXwdvMitFJG

[woeful minnow]

I need help with this question if anyone can assist?

Show that the order of 2 modulo F_n all less than or equal to 2^(n+1) with F_n = 2^(2^n)+1 is the nth Fermat Number.

$ord_{F_n}(2) \leq 2^{n+1}$ with $F_n = 2^{2^n}+1$ is the $n$th Fermat Number.

[torn escarp]

just fyi on formatting if you put _ or ^ to keep everything together use {}

[woeful minnow]

ah kk

[sterile pumice]

Suiadan

[woeful minnow]

huzzah

[woeful minnow]

For some reason I smell proof by induction on this (though it doesn't necessarily need to be a proof)

[torn escarp]

I think it can be done directly for n, but I've not thought about it too hard so could be wrong on that

especially cause I'm thinking I've proven that the order is exactly 2^{n+1} and doesn't seem like it's too much extra work to say that

so kind of suspicious I'm wrong since I've proven something stronger

[woeful minnow]

well tbf there is no restriction on "n"

[torn escarp]

what have you got so far?

[woeful minnow]

"By definition of order, $ord_{F_n} => 2^d$ is congruent to 1 (mod $F_n$) for some $d \in Z$.
This implies that $2^d$ is congruent to 1 (mod $2^{2^n}+1$) by substitution.
Note that, $F_n = 2^{2^n}+1$ which implies that $F_n -1 = 2^{2^n}$ by subtracting 1 from both sides of the equation, since...

Seems legit

This is targetting a different route than induction btw

Dunno if I can somehow use $2^{F_n-1}$ is congruent to 1 (mod $F_n$) by Fermat's Little Theorem, but I am unsure if Fermat Numbers are prime?

[sterile pumice]

Suiadan

[torn escarp]

yeah looks pretty good, I think you sorta left some parts out here in the first line at least

I'm thinking you meant to say $d=ord_{F_n}(2)$

[sterile pumice]

Suiadan

Merosity

[woeful minnow]

yuh, I should clarify that 😓

[torn escarp]

you're on the right track, I wouldn't worry about Fermat's little theorem though here

[woeful minnow]

Nah?

[torn escarp]

we just need an upper bound and you're pretty close I feel

[woeful minnow]

dunno, I feel lost on how to tie together the conclusion to my progress so far... 😦

[torn escarp]

you have 2 to a power congruent to -1 mod F_n

that's nearly 2 to a power congruent to 1 mod F_n

[woeful minnow]

hmm

[torn escarp]

how can you make -1 into 1

$$2^{2^n}\equiv -1 \mod F_n$$

[sterile pumice]

Merosity

[woeful minnow]

Implies $2^{F_n-1}$ is congruent to $F_n-1$ (mod $F_n$)

[sterile pumice]

Suiadan

[woeful minnow]

oh it's "equiv" kk

[torn escarp]

hmm the F_n in the exponent wasn't what I was going for

I'm thinking more like comparing these two
$$2^{2^n}\equiv -1 \mod F_n$$
$$2^d\equiv 1 \mod F_n$$

[sterile pumice]

Merosity

[woeful minnow]

Implies $$2^{(2^n+1)-1} \equiv (2^n+1)-1 mod F_n$$

[sterile pumice]

Suiadan

[torn escarp]

using the fact that (-1)^2 = 1

[woeful minnow]

Implies $$2^{(2^n)} \equiv (2^n) \mod F_n$$

[sterile pumice]

Suiadan

[woeful minnow]

hmm

[woeful minnow]

How did you get this EQ?

I feel silly

[woeful minnow]

Cuz I think I know what you mean by this

[torn escarp]

I see, I skimmed over that

[torn escarp]

reduce your $F_n-1 = 2^{2^n}$ modulo $F_n$

[sterile pumice]

Merosity

[torn escarp]

or reduce the definition of F_n from the beginning and rearrange it a bit

[woeful minnow]

hmm

I could say that $F_n = 2^{2^n} - (-1)$ by algebra and by definition of congruences, we obtain $2^{2^n} \equiv -1 \mod F_n$

[sterile pumice]

Suiadan

[woeful minnow]

I think that's how you got that!

[torn escarp]

nope

[woeful minnow]

Damn

[torn escarp]

mod 2^{2^n} is entirely different than mod 2^{2^n}+1

[woeful minnow]

wait that was my first way

[woeful minnow]

Consider this one

[torn escarp]

yeah that's right

[woeful minnow]

Squaring both sides:
$(2^{2^n})^2 \equiv 1 \mod F_n$

[sterile pumice]

Suiadan

[torn escarp]

yeah that's it

[woeful minnow]

Simplifying:
$2^{2^n}2^{2^n} \equiv 1 \mod F_n$

[sterile pumice]

Suiadan

[woeful minnow]

$2^{2^n+2^n} \equiv 1 \mod F_n$

[sterile pumice]

Suiadan

[woeful minnow]

$2^{2*2^n} \equiv 1 \mod F_n$

[sterile pumice]

Suiadan

[woeful minnow]

$2^{2^{2^n}} \equiv 1 \mod F_n$ ? <===REDACTED

seems wack?

[torn escarp]

Yeah whack haha

$$(2^a)^b = 2^{ab}$$
$$(2^{2^n})^2 = 2^{2^n2} = 2^{2^{n+1}}$$

[sterile pumice]

Merosity

[woeful minnow]

felt

lmfao

Yeah I'm trippin

[torn escarp]

back to elementary school! 😛

[woeful minnow]

LMFAO

https://tenor.com/view/skull-issues-gif-13031152103567454559

[torn escarp]

yeah regular exponent rules but there are a bunch of exponents up there so I see the pain haha

[woeful minnow]

right right

Implies $2^{2^{n+1}} \equiv 1 \mod F_n$

[sterile pumice]

Suiadan

[woeful minnow]

Ohhhhh shoooot

Implies d must divide 2^(n+1)

pog

therefore $d \leq 2^{n+1}$

[torn escarp]

yeah, now weird thing is all divisors are just smaller powers of 2, so I think we can prove this really is the order of 2 now

[woeful minnow]

by definition of order, that d is the smallest positive integer such that 2^d \equiv 1 \mod F_n

[sterile pumice]

Suiadan

[woeful minnow]

hmm

[torn escarp]

but I realize why that conclusion I jumped to is wrong haha

[woeful minnow]

I know the problem doesn't ask me for that but I'm curious

[woeful minnow]

Is it by this proof that we cannot garuntee it?

[torn escarp]

nah, this just gives us an upper bound

we'd have to get more in depth in what 2^{n+1} is mod phi(F_n) I think to really determine the order

[woeful minnow]

yeah that's what I was thinking on how that might follow

Thanks for your help @torn escarp !

[torn escarp]

you're welcome!

[vast dove]

Prove that a sum of integers is odd iff the sum of squares of those integers is odd

@torn escarp

Why is this true

Oh this is obvious if u work mod 2

0^2 =0 and 1^2=1 mod 2

[torn escarp]

you're welcome 😉

[peak root]

Please help with the reasoning of the last 3 lines here.

[still flare]

It's unclear what a, a^2, ..., a_phi(n) means.

If you mean a, a^2, a^phi(n) instead, then this is clearer.

The reasoning being simply that all of a, a^2, ..., a^phi(n) are distinct mod n and relatively prime to n, by definition they must each be congruent to some a_i as chosen.

[peak root]

the one with subscripts mean different numbers

[still flare]

But you wrote a, a^2 with the two being superscript and then a_phi(n) with phi(n) subscript!

So again, it is unclear what that means.

This is just after your therefore symbol whoops, see below

The last line

[peak root]

the set with superscripts mean the powers of a while the subscripts denote that there are n different integers

[still flare]

I know. I am fully aware.

Let me explain one more time

On the last line you write $a_1, a_1^2, \dots, a_{\phi(n)}$. Since you put the last thing in subscripts here, although the first two appeared to be superscripts, it is unclear what this set is.

[sterile pumice]

$\mathbf{Boytjie}$

[still flare]

I think you meant $a_1, a_1^2, \dots, a_1^{\phi(n)}$.

Whoops typo

[peak root]

Oh I am sorry

[sterile pumice]

$\mathbf{Boytjie}$

[still flare]

In which case, I have explained the reasoning here I hope.

[peak root]

Yes, you are right

[peak root]

But why? which theorem or lemma is being used to come to this conclusion

[still flare]

Or uh if I'm being actually correct here, you mean $a, a^2, \dots, a^{\phi(n)}$

[sterile pumice]

$\mathbf{Boytjie}$

[peak root]

Yes, this

[still flare]

You have phi(n) things out of a list of phi(n) things, so you have all the things.

[peak root]

I am sorry for the confusion

[peak root]

This is the correct one

[still flare]

Is this clear or no?

[peak root]

No, its not clear

[still flare]

a_1, ..., a_phi(n) is a list of phi(n) things.

Every one of the a^i is one of those things

We have phi(n) of them, because they are all distinct.

So we have all of them.

This is nothing to do with modular arithmetic and everything to do with counting

If I show you a list of 100 things and I show you another list of the same 100 things, then they must be the same list but in a different order.

[peak root]

Ohhhh okay got it now

Thanks a lot

[charred roost]

To be clear, the proof you gave doesn't really explain why a, a^2, ..., a^phi(n) are distinct. It is true because a is a primitive root, so a has order phi(n), and if a^i = a^j for 1 <= i < j <= phi(n) then a^(j-i) = 1, contradicting the fact that a has order phi(n)

[high sorrel]

Is there an efficient way to determine if a high degree polynomial is irreducible mod 2? For instance, something like x^180+x^45+1 or x^36+x^27+1 etc.

[forest plank]

Well these polynomials seem kind of special

[long lion]

i guess you could try like adjoining a root $\alpha$ of $x^4 + x + 1$

[sterile pumice]

LY

[long lion]

and then adjoin a root $\beta$ of $x^{45}- \alpha$

[sterile pumice]

LY

[long lion]

and try showing that $[\mathbb{F}_2(\alpha, \beta):\mathbb{F}_2] = 180$?

[sterile pumice]

LY

[long lion]

just a suggestion

[high sorrel]

alr, I'll try that, thanks for the tip!

[tranquil nacelle]

@everyoneThe remainder of 10 divided by 2 + 3ω. How do we find this?

[patent acorn]

what's ω?

[fallen granite]

@tranquil nacelle maybe try modulus, It's basically defined based on remainder. Assuming w is some positive integer; for w >2 the answer is just 10, and then for w = 0,1,2 it's 10 mod(2,5, and 8) so that is 0, 0 and 2.

Btw, was discord out for just or was anyone else unable to reply to messages for a while?

[forest plank]

2+3w is a factor of 7, so the remainder is 3. (Also using a fact that 2+3w is a prime with norm 7, so all its residue classes are: 0,1,2,3,4,5,6)

[fallen granite]

@forest plank 2 +3w is a factor of 7? maybe w is not an arbitrary positive integer then, what is w?

Also, can some one help me with this, I was trying modular obstacle but I'm missing something or everything cause I cant figure it out

[forest plank]

I guess w is the root of x^2 + x + 1 = 0

[forest plank]

Hmm I think reduction modulo 7 works to get a contradiction 😊

[fallen granite]

I tried 3 already but I'll go al the way through with 7 this time

@forest plank It had solution mod 7 and mod 3 doesn't seem to give any contradictions, maybe there's some other way than modular obstacle?

[forest plank]

x^2 - z^6 = 5 (7)

All squares m7 are 0,1,2,4

z^6 is either 0 or 1

[fallen granite]

I must be tired or something, I wonder what I did when I checked

Thanks

@forest plank I must have checked for x^2 - z^2 for what ever reason

[stuck mulch]

when in doubt try mod 7

[zenith junco]

can anyone proof that 1+1=2,is it even proved

[west glade]

you need to think about what the symbols 1,2,+,= even mean

afterwards the proof will depend on your definitions

[swift pilot]

Is it true that a*10 = 5 mod 35 iff a*2 = 1 mod 35?

[charred roost]

No, only the <= implication is true. If 2a = 1 mod 35 then multiplying by 5 gives 10a = 5 mod 35, but going the other direction requires you to divide by 5, which is not possible modulo 35

[patent acorn]

a = 4 is a counterexample to the => direction

[river lotus]

Can anyone explain to me why the proof formula on ECDSA just works?!! It seems so un-intuitive to me! Even on curves with smaller order it just works!

Are there any geometric patterns than can be shown when doing scalar addition or doubling when looking at the integer points ?

[rotund nebula]

Opinions of this Collatz proof? https://arxiv.org/pdf/2008.13643

[glass cosmos]

for this problem. Do I read it as (9^9)^9 or 9^(9^9)?

I know I just need to do mod 100

[carmine tide]

The second one

[glass cosmos]

😭

[still flare]

The first would be written $(9^9)^9$, not $9^{9^9}$.

[sterile pumice]

$\mathbf{Boytjie}$

[glass cosmos]

I would have said the same for the latter unless there is some unspoken rule if we have exponents to exponents we work our way top to bottom

[ember trellis]

im pulling my hair out over this question

[candid lantern]

if d|a and d|b then d is a factor of their gcd

[ember trellis]

in fact its a multiple of gcd

and i can't understand how I can get to a point where d=0

d can be any multiple of 10, but this contradicts gcd = 5

and im stuck after this point

[candid lantern]

hm

i don't get what ur saying

if $d|a$ and $d|b$ then $d|5$

[sterile pumice]

rain

[candid lantern]

that means $5 = dk$

[sterile pumice]

rain

[ember trellis]

d is an even integer so $\exists k \in \mathbb{Z}$ such that $d=2k$.

[sterile pumice]

onlinebelief

[ember trellis]

So, that is a contradiction

[candid lantern]

yes

[ember trellis]

so hmm

[candid lantern]

thats it

ur done

[ember trellis]

?

really

how so

[candid lantern]

Ok

we have $d|5$

[sterile pumice]

rain

[candid lantern]

meaning $d$ is a factor of $5$

[sterile pumice]

rain

[candid lantern]

there are no even factors of 5

[ember trellis]

right?

[patent acorn]

...yeah the problem is weirdly stated but "this situation is a contradiction, therefore d = 0" is a valid inference

[ember trellis]

isnt it $0 \rightarrow q \Leftright arrow 1$

[sterile pumice]

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

[candid lantern]

i don't know number theory but why is $d=0$ eeven a valid solution lol

[sterile pumice]

rain

[patent acorn]

it isn't

[candid lantern]

is it convention

[ember trellis]

we havent necessarily proven $q$

[sterile pumice]

onlinebelief

[candid lantern]

can you recompile the earlier statement

idk what ur saying

[candid lantern]

im guessing its convention or something

but i would rather say there is no solution

[patent acorn]

no i think the person who wrote the problem was just wrong

[ember trellis]

isnt it $0 \rightarrow q \Leftrightarrow 1$

[sterile pumice]

onlinebelief

[candid lantern]

lolprobably

[patent acorn]

but the problem as stated is still true

[candid lantern]

what does $0 \to q$ mean

[sterile pumice]

rain

[patent acorn]

it's just weird

[ember trellis]

contradiction implies q

[patent acorn]

there are no solutions, and therefore all of the solutions satisfy d = 0

[candid lantern]

your notation is not standard, what does 1 mean

[ember trellis]

oh 1 is a tautology

[patent acorn]

it would also have been valid for the problem to end with "Prove d = 7"

[candid lantern]

i understand ur going for a vacuous solution but i dont agree

thats like saying $x^2+1=0$ for real $x$ satisfies $x=2$ because no solution

[sterile pumice]

rain

[candid lantern]

@ember trellis what is your confusion?

do you agree that no positive integer can be d?

[ember trellis]

there is a contradiction with the hypothesis

how would we prove d=0 if we cant use the hypothesis

[patent acorn]

we can use the hypothesis, to get a contradiction, and then a contradiction implies everything

or an equivalent view: we can prove d=0 by assuming d != 0 and then deriving a contradiction, which in this case can be done by completely ignoring the hypothesis that d != 0

[glass cosmos]

what about for mod n (sorry didnt read anything prior)

[glass cosmos]

Does zero count as a quadratic residue of n?

Just curious because I feel like it makes some case work some proofs annoying about whether I can assume gcd(a,n)=1

[exotic sparrow]

Depends on the author

It doesn't really matter because the zero case is always trivial

[glass cosmos]

The hint for this problem suggest to me the author doesn't even consider a = 0 mod p

Something like this question is why I asked

Because a' won't exist if it isn't a is. Multiple of p

[exotic sparrow]

Yes

Then the author doesn't consider zero a QR

[eternal sequoia]

any hints as to how one would go about proving that the sum of coefficients of a trinomial expansion (a+b+c)^n is 3^n (for n>=3)?

[surreal tangle]

Hint: ||think of it as a function of a,b, and c||

This one ruins it : ||evaluate this function at a certain nice point||

[surreal tangle]

This holds true for n = 1 and 2 also, btw

[patent acorn]

and for n=0

[surreal tangle]

Indeed

[eternal sequoia]

Each term is:
n!/(i! j! k!) * x^i * y^j * z^k
So the sum of all coefficients is summation(n!/(i! j! k!))

(i + j + k) = n

[surreal tangle]

That is right, what i am saying is, think of it as a function depending on a,b, and c. Now what is the advantage of thinking about it as a function? You can do a certain very nice thing with these functions

[eternal sequoia]

you can evaluate the function for different values of the variables?

[surreal tangle]

Yes

So, how do you plan to use that?

[eternal sequoia]

sorry if this sounds stupid but we'd get 3^n if x=y=z=1 but I'm not sure how that makes sense for a general case

[surreal tangle]

That isnt stupid, and it is absolutely correct

Think about why it works

[eternal sequoia]

OHHH

got it

[surreal tangle]

When you expand $f(a,b,c)=(a+b+c)^n$, you will get a sum $f(a,b,c)=\sum_{\overset{i+j+k = n}{0 \leq i,j,k \leq n}}a_{i,j,k}a^{i}b^{j}c^{k}$ and we want to determine $\sum_{\overset{i+j+k = n}{0 \leq i,j,k \leq n}}a_{i,j,k}$ which is precisely $f(1,1,1)=3^n$

[sterile pumice]

quicdoom

[surreal tangle]

1 and 0 are great numbers. You can infact evaluate the coefficients of just the terms with powers of a and b but not of c, and other nice things

[eternal sequoia]

I've been thinking--would it be possible to find the number of terms for given n where i or j or k = 0?

[surreal tangle]

That is a nice question that leads into a very nice concept. Lets say i=0, then we want to find the number of terms that only have indices of j and k. That is, we want to find the number of solutions to j+k=n, 0<=j,k<=n(why?). Now that we have reduced it to a problem about solutions to an equation, try to think of a way to solve this

[surreal tangle]

This is possible and has nice generalisations

[eternal sequoia]

is the total number of terms 3(n+2) for n>0?

[surreal tangle]

Now we can generalise to ask, what is the number natural of solutions to the equation x1+x2+...+xk = n, for k <= n?
This is a relavant wikipedia article, and theorem 1 is what i just asked you about above.

https://en.wikipedia.org/wiki/Stars_and_bars_(combinatorics)

[eternal sequoia]

is there a way to find these 3(n+2) terms (or their sum maybe)

[surreal tangle]

There are two methods to the solution. One is what is known as stars and bars and anothee very powerful technique of generating functions

[surreal tangle]

Well you know the terms, since you know the trinomial coefficient. For their sum, think back to what we just did

[eternal sequoia]

but I... don't know the terms

[surreal tangle]

You do,

[eternal sequoia]

that, yes

but that just gives me (say for i = 0)

summation(n!/(j!)(n-j)!)

[surreal tangle]

Do you want their sum? Then read what i wrote for the sum part

Evaluate the function at nice points

[eternal sequoia]

I do

[surreal tangle]

What would be a good point to evaluate the function at , for the sum of terms with only j and k indices and i=0

[eternal sequoia]

j=0? but that doesn't make sense

[surreal tangle]

a=0,b=1,c=1

f isnt a function of j to be evaluated at j

[eternal sequoia]

oh right

[eternal sequoia]

by the way, was the 3(n+2) expression correct?

for n=3 at least it isn't matching

[surreal tangle]

Oh wait i miscounted, its 3(n+1)

[eternal sequoia]

3n is matching

3(n+1) isn't

[surreal tangle]

i+j=3 has 4 solutions (0,3),(1,2),(2,1),(3,0). Similarly there are 4 for j+k=3 and 4 for k+i=3 so in total there are 12 = 3(4)=3(3+1) solutions

[eternal sequoia]

there are n+1 solutions to i + j = n (similarly for j + k = n and i + k = n) so total 3(n+1) solutions
but there's also 3 more cases where k or j or i = n (so i+j=0 and so on)
so shouldn't the total number of such terms be 3(n+1) + 3?

[surreal tangle]

You are trying to solve i+j=n for 0<=i,j<=n

Where are 3 variables at a time coming in form

You are not simultaneous solving anything here

[eternal sequoia]

yes, it should be just 3(n+1)

didn't realize I was recounting 3 cases

but even then, it doesn't match

for (x+y+x)^3

the number of terms where i or j or k = 0 is 9

using the formula, it should be 12

I checked for n=3 and n=4, and it seems 3n gives the number of terms where i or j or k = 0

[surreal tangle]

That formula wont work here. If you apply it here you are double counting the solutions that look like (2,1) (alternatively (1,2)). They appear once extra 3 times. So you have 12-3 =9

That formula just gave you the number of nonnegative solutions to i+j=n

[eternal sequoia]

I read up on stars and bars

Using that we get the ||number of terms which have at least one of i, j, k = 0 as (n+1)(n+2)/2 - (n-1)C3||

also noticed that there's a pattern which we can use to figure out ||the (n+1)(n+2)/2 term (i.e. total number of non-negative solutions):
for n=1, solns = 3
for n=2, solns = 4
for n=3, solns = 6
for n=4, solns = 10, and so on
the number of non-negative solutions are in an AP where the common difference is in AP as well (with common difference 1). If we find t_n we get the same term (n+1)(n+2)/2||

[eternal sequoia]

for the sum of terms ||this does work, yeah. We get 2^n as the sum for i=0, and similarly for j=0 and k=0, so sum of all required terms = 3 * 2^n - 3 (because we're counting (i, j), (j, k), (i, k) = (0, 0) each one extra time||
||Since the total number of terms is 3^n, we can just subtract the expression we obtained above to get the sum of terms where i, j, k > 0.||
So the final expression seems to be ||3^n - 3*2^n + 3|| which does give the expected results

[alpine lantern]

could someone help me solve this please

with steps

[wise edge]

can anyone offer their perspective?

ooh can I do $2m \leq n$

[sterile pumice]

Dinosavr

[wise edge]

Then what

[wise edge]

ooooooh Assume by contradiction that $m$ is a perfect number. We'll write $n=m \cdot r$ for some natural $r >1$. Then $$\sigma(n)=\sum_{d \mid n}d\neq \sum_{d \mid m} dr=r \sum_{d\mid m}d=r\sigma(m)=2qr=2n$$. Thus we got than $\sigma(n)\neq2n$

[sterile pumice]

Dinosavr

[wise edge]

smth like that?

$r \cdot 2m = 2n$ ***

[sterile pumice]

Dinosavr

[eternal sequoia]

for r > 1, shouldn't it be m = nr since m | n?

[exotic sparrow]

m | n means m divides n

[eternal sequoia]

oh, oops

I read it as m is divisible by n

[eternal sequoia]

Assuming $m$ is a perfect number, sum of all proper divisors of $n$:
$$\sigma(n) - n = n = 2m + \sum_{d \mid n, d \nmid m} d $$
$$\sum_{d \mid n, d \nmid m} d = n-2m = k (say)$$. $k>0$ but $n-2m < 0$ (???)

where am I going wrong?

[sterile pumice]

DumbledoreSaidCalmly

[bold badge]

Suppose $m$ were perfect. Since $m | n$ and $m \neq n$, we can write $n = km$ for some $k>1$. We can write some divisors of $n$ explicitly by using the fact that $d | m \implies kd | n$, and the sum of divisors of this form can be simplified as $\sum_{d | m} kd = k \sum_{d | m} d = 2km$. This gives us that $\sum_{d | n} d \geq 2km$, and furthermore, since $1 | d$ but $1 \neq kd$, we have that $\sum_{d | n} d + 1 \geq 2km$. This, however, means that $\sum_{d | n} d > 2km$ and thus $\sum_{d | n} d \neq 2n$, therefore $n$ cannot be perfect.

[sterile pumice]

FEIN FEIN FEIN FEIN FEIN FEIN FE

[bold badge]

should work

And if you restate the question equivalently as like “show that if n is a multiple of a perfect number m such that n>m then n cannot itself be perfect” then it’s just like a direct proof

Fun problem

[bold badge]

Yeah this is the strategy I took as well

you got the gist of it but need to justify the “sum of d =/= sum of dr” step

I just chose like the simplest thing that divides n but can’t be of the form dr which is 1 and that’s enough to give a strict inequality

[bold badge]

Use the fact that a/b mod m will be an integer n satisfying bn \equiv a mod m whenever b and m are coprime (which in this case they are cause gcd(15,11) = 1)

[harsh grove]

I have a basic doubt in Cryptography specifically the SHA-512 topic. Can anyone help regarding that topic?

[patent acorn]

well probably if you ask an actual question someone can help with that question

[harsh grove]

Ok well, from what I know, in SHA 512, the padded message consists of the actual message + padding + 128 bits for length such that the length of this entire thing is a multiple of 1024.
In my book its also written that we pad a message so that its length remains congruent to 896 modulo 1024.
How can both these statements be true simulaneously?

Like suppose if we have a message of length say 1700 bits. If we want to make it congruent to 896, we will need to add (896*2 - 1700) i.e. 92 bits of padding. And 128 bits is fixed for length. This means that the length of the final message is (1792+128) = 1920 which is not equal to a multiple of 1024

Am I missing something somewhere?

[patent acorn]

if you add 92 bits of padding, then the length of the message is 1792, which is not congruent to 896 mod 1024

the correct amount of padding is 1024 + 896 - 1700 = 220 bits, and then 1700 + 220 + 128 = 2048 is a multiple of 1024

[harsh grove]

OH

I was confusing it with mod 896. Thanks!

[undone cypress]

how would i undo the affine cipher

like if i have (u*x + v) % m and then i have u v and m

actually let me think harder lmao

https://tenor.com/view/ten-hag-gif-26473065

[undone cypress]

i think i got it

[analog onyx]

Im working on decrypting a message that was encoded using El Gamal. I was given p, alpha, beta, r and t. The value of r is relatively small, so I think i should be solving the discrete log on r = alpha^k mod p. However, p has about 150 digits, so sage or alptertron can't do it in a reasonable amount of time. p is also 3 mod 4, so I am not really sure how to proceed with this.

[analog onyx]

i figured it out.

[tranquil nacelle]

@everyone Let p be a prime prime with p ̸ ≡ 1 (mod 7). Prove that every integer is a seventh power
modulo p. In other words, prove that for every a ∈ Z, there exists x ∈ Z such that x7 ≡ a
(mod p).
Hint: In the case p ∤ a, use the extended Euclidean algorithm on GCD(p − 1, 7) and Fermat’s
Little Theorem.

l need help with this question

if you mind sending the proof that would be amazing

[torn escarp]

what have you tried so far

[tranquil nacelle]

i tried starting off with the 7 does not divide p -1 and then use EEA

and l dont know how to write the a = qb + r

[torn escarp]

I don't think you really need to go through the algorithm, I think they just want you to see there's an m and n such that m(p-1)+n7=1 and use this

does that make sense how you could use that if you think of the exponents @tranquil nacelle?

[long lion]

i mean, an alternate soln would be

||show that x^7 = 1 mod p => x = 1 mod p||

||then think about why that's enough||

[exotic sparrow]

you can also ||take a primitive root||

[torn escarp]

since OP bailed I'll just finish it for everyone else here. This means n is an inverse to 7 mod p-1, so if you want to find x^7 = a mod p you just need to raise both sides to n and get x=a^n mod p.

[royal bear]

in an artical im reading it gives an alternative form of the continued fraction of e

where the first 2 has been split into 1,0,1

ofc this means that the second convergent p1/q1 is not defined

the author asserts this is fine and it doesnt matter

why can we disregard the fact we cant truncate it at 1?

[still flare]

Suppose I have a sequence 0.1, 0.11, 0.111, 0.1111, etc.

I claim that this converges to some value.

But notice that I could throw away any number of initial values in the sequence

I could start at 0.111111111111111111111 and carry on from there and I'd still get the same value on convergence.

The same thing is happening here.

We are just ignoring some initial terms. They do not matter. Only the behaviour in the limit matters, and that is preserved.

(Paradoxically, you could throw away any finite number of the terms in any sequence, and the limit is still the same. So in some sense none of the terms matter)

[royal bear]

i just find it weird to have it set up so that one of the convergents is undefined

but yh, the limit wont change

[edgy cedar]

Hi

[feral olive]

Hello. I would like to proove that if

A1 congruent to a2 mod m

And

B1 congruent to b2 mod m

Then

A1 +/- b1 and a2 +/- b2 mod n

And

A1 × b1 congruent to a2 × b2 mod n

Is my solution corrrct please?

[forest plank]

I think correct

[feral olive]

Great! Thanks you very much!

Could i reuse same method for addition and multiplication please?

[charred roost]

It's not correct, you seem to write a1 - a2 = mx and b1 - b2 = my, then (a1 - a2) - (b1 - b2) = mxy, which is just wrong. Also it's very hard to read because of

• blurryness
• your handwriting
• you're using x both as a variable and as multiplication
• lack of any explanation between the equations. A proof should use natural language, it shouldn't be just symbols

[feral olive]

let me rewrite in latex please then

let $a_1 \equiv a_2 \mod n$ and $b_1 \equiv b_2 \mod n \newline$
then $n \mid  a_1 - a_2$ and $n \mid b_1 - b_2 \newline$
so:
$a_1 - a_2 = n \mul x \newline$
$b_1 - b_2 = n \mul y \newline$
so:
$a_1 - a_2 = n \mul x \newline$
$b_1 - b_2 = n \mul y \newline$

[feral olive]

latex is not generated anymore!!!

let $a_1 \equiv a_2 \mod n$ and $b_1 \equiv b_2 \mod n \newline$
then $n \mid  a_1 - a_2$ and $n \mid b_1 - b_2 \newline$
so:
$a_1 - a_2 = n \mul x \newline$
$b_1 - b_2 = n \mul y \newline$
so:
$a_1 - a_2 = n \mul x \newline$
$b_1 - b_2 = n \mul y \newline$

[sterile pumice]

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

[feral olive]

untils there is there a mistake please?

[smoky burrow]

Yes, it's true that there exist $x,y \in \mathbb{Z}$ such that $a_1 - a_2 = nx$ and $b_1 - b_2 = ny$. Now what?

[sterile pumice]

Cufflink

[feral olive]

but not for any?

[still flare]

Not for any, yes. For some specific x and y.

[smoky burrow]

Don't ask us. If you think it's true for "any" x, try out a few values as a sanity check. Is it true that if n | a-b then a-b = x*n for any integer x?

Ok, well, try a = 100 and b = 75. 5 divides 100 - 75. Is it true that 100 - 75 = x*5 for any integer x?

[feral olive]

1 congruent 13 mod 12

1 = 13 - 12 and not 12 divides 1 - 12

then no there is a mistake

or 11 = 12 multiplicated by x

that could only be wrong

12 = 1 - 13

no it is right

[smoky burrow]

Something like

100 - 75 = x*5 for any integer x

should appear immediately incorrect. You have a specific number on the left-hand side and you have a variable on the right-hand side that you can make any value you choose. The right-hand side will be a different value for each x you care to choose.

[feral olive]

12 = 1 - 13
12 = 1 - 13 x 1 = 12

[smoky burrow]

12 doesn't equal 1 - 13

[feral olive]

-12 sorry

[smoky burrow]

Yes, it's true that 1 - 13 is divisible by 12. That doesn't mean 1 - 13 = x*12 for any integer x.

In fact, there's exactly one integer x for which it's true: x = -1

It's false for every other value of x.

[feral olive]

12 = 1 - 13 + 12 mul 2

then yes it is ok

because 2 - 3 = - 1 and then 2 cong 3 mod 12 = 2 - 3 + 12 = 11

[feral olive]

could rewrite so that n divides a1 + a2 mod n please?

[feral olive]

1 - 13 =mod 12 = -1 + 12 = 11. is it correct

please?

[smoky burrow]

I don't know what you're trying to express.

[feral olive]

I would like to reexpress this formula

I mean that 6 + 9 = 3 because 6 cong 9 = 3 as 6 + 9 = 15 - 12 then 15 - 12 = 3

ahhhhhhhhhhhhhhhhhhh ok!

a cong b mod n
means:
a is the remainder of b divided by n

then

ah no

ok!

I see my mistake

I litterally ignore what is a umodulo!!!!!

a cong b mod n means actually that if a divided by n, remains b