elementary-number-theory

[hushed sable]

Is that the factoring -1 that I wanted to do originally?

[rugged locust]

I thought with my hint it was solvable

[hushed sable]

Yeah I'm just smushing symbols together rn, maybe give me another minute I should be more self sufficient

It just seems to barely not fit

The dopamine when I just got it

[opaque arrow]

Hello, I received some questions as homework
As I'm solving the question, I thought about how I can factor a number like 100!
ofc I could use Legendre's formula for prime factoring of a factorial number
But I thought maybe I could factor it as other factorials like
3!*5!=6!
for example
Is there any known formula or way to factor n! as a product of other factorials?

[kindred fulcrum]

לחם

[kindred fulcrum]

this seems like a complicated problem

but legendre's formula tells you a lot

since 97 is prime, by legendre you know v_97(100!)=1 and you must have 97! as one of the factorial factors

[patent acorn]

well, 97! or something bigger

it can't be 99! because 100 can't be written as a product of factorials, it has a prime factor of 5 but not of 3

98! fails for a similar reason, 99 * 100 has a factor of 11 but not of 7

98 * 99 * 100 is 2^3 * 3^2 * 5^2 * 7^2 * 11

[kindred fulcrum]

yeah yeah

[patent acorn]

which doesn't work because 11! has too many factors of 2

so in fact it's impossible, excluding the trivial "100! = 100! * 1!" things

[kindred fulcrum]

I think in general this is a hard question

[regal summit]

Doesn't seem like theres an algorithm to solve it in general

Which makes sense bc it concerns primes

[unique cypress]

Question to ask yourself: is the factorization unique

[opaque arrow]

thats me!

[opaque arrow]

i bet its not

to many options

😄

thought that I needed to somehow factor 100! into a smaller number and then multiply them, but it has too many prime factors to use the prime factorization of it in my opinion

[kindred fulcrum]

מה קורה!

[kindred fulcrum]

Did you solve it?

[opaque arrow]

ישראלי?

[opaque arrow]

no

בן כמה אתה לפני שאני מריץ כאן במ

[kindred fulcrum]

מה קשור הגיל שלי?

[opaque arrow]

סתם זה לא באמת במ פשוט זה חידה של אמן

לקראת מיונים צהליים

[kindred fulcrum]

אני יותר מבוגר ממך כנראה 🙂

[opaque arrow]

סבבה

[kindred fulcrum]

תן לי לחשוב על זה

[opaque arrow]

קח תזמן אני מתייעץ פשוט עם אנשים

ותוך כדי מנסה לפתור לבד

תודה על העזרה בכמ

[kindred fulcrum]

הצלחתי בבערך 200 צעדים

[opaque arrow]

200 צעדים זה הפתרון הטריוויאלי אני חושב לא?

[kindred fulcrum]

כן

יש לי רעיון שקשור לפירוק לראשוניים ומה שאמרת עם נוסחת לג'נדר

אני בודק כמה צעדים זה מביא

[opaque arrow]

אני גם חושב על זה בבעיה זה ה2^97

אני לא מבין איך להשיג אותו

[kindred fulcrum]

הצלחתי 137

הרעיון:
להסתכל על הפירוק לראשוניים של 100! ולעבור ראשוני ראשוני שמחלק אותו

נתחיל מצעד אחד שמביא אותנו ל-
[1, 0, 0, 1]

מכאן נשתמש באפס הימני כמקום לשמור את המספר הראשוני שעכשיו אני עובדים איתו

אז נשים בו 2 עכשיו

נשים לב שהחזקה של 2 בפירוק לראשוניים של 100 זה 97 או 1100001 בבינארי

אז נשים במקום השני משמאל את 2 ונכפיל את המספר השמאלי ביותר ב-2

לאחר מכן, נכפיל את המקום השני משמאל בעצמו עד שנגיע ל-2^32 שזה מקביל לספרה הבאה שהיא 1 בייצוג הבינארי

ואז נכפיל את המקום השמאלי ב-2^32

נעשה את זה גם עבור 2^64 ונקבל 2^97 במקום השמאלי ביותר

מכאן נקדם את המספר הראשוני ב-1 ל-3 ונמשיך ונעשה אותו תהליך גם ל-3 בשביל להכפיל את המקום השמאלי ב-3^48

מכאן, אפשר להפוך את המקום הכי ימני ל-2 כי כל הראשוניים מכאן הם אי זוגיים

ואז ממשיכים ככה עד שעברנו על כל הראשוניים עד 100

137 זו הערכה גסה

כנראה יותר כמו 120

[opaque arrow]

אני אנסה

אני בדיוק בתהליך איך לעבוד על הראשוניים

לדעתי כדאי לבנות ככה את הכפולות
[1,0,0,0]->[1,2,0,0]->[1,2,4,0]->[1,2,4,16]->[1,2,2^8,16]->[1,2,2^8,2^16]
וכן אלה

[kindred fulcrum]

זה אותו דבר כמו שאני אמרתי בערך רק אולי אתה חוסך צעד אחד בהתחלה

אה אולי זה חוסך קצת יותר עבור הראשוני 2

[opaque arrow]

כן כן זה אחלה משם נראה מה נעשה

[abstract ferry]

why is ENT full of non-english

#elementary-number-theory is not a help channel

[kindred fulcrum]

sorry for that, we didn't really expect anyone else to join the conversation

[opaque arrow]

mb

[dull tulip]

@opaque arrow what language is itt its so cool

[kindred fulcrum]

Hebrew

[dull tulip]

Wow

[opaque arrow]

Hebrew !

some says its the enchanting table language

[abstract ferry]

nah it's ok btw the language looks very cool 🔥🔥

[opaque arrow]

most non latin languages look cool
most of the people are just sick of seeing those latter

letters

in my oppinon greek is looking so good

they speak math

[limber verge]

phi rho 💀

[wanton gorge]

"I got a video on Number Theory, and in some parts it says: "Full Course on Coursera", so I guess that’s where it’s from. You can find it on YouTube under the title: "Number Theory and Cryptography Complete Course _ Discrete Mathematics for Computer Science"

[sweet lichen]

Wait! Do I have to search "Number theory and cryptography complete course_ discrete mathematics for computer science" ?

Doesn't number theory comes in discrete maths?

[broken phoenix]

How to divide in non-decimal bases?

For example let base be 8. I know multiplication is done by for example 6•5 = 30 -> 30/8 = 3 + remainder 6. The result is 36.

Division will usually not be in the base right, so let's say 42/4 in base 8 but 42 isn't in that base or we already accounted for it? Then 42/8 = 52 in base 8 and then divide like normal or what?

[kindred fulcrum]

computing 42/4 in base 8 is done with the normal algorithm

the result is 10.4

[broken phoenix]

Is this true of any base? What about 99/8? Neither numbers belong in base 8 so we will transform them?

99 = 123 and 8 = 10 so 123/10 = 12,3?

[patent acorn]

...i feel like you're confusing numbers with representations in some way

[west glade]

if you want to work in base 8 then of course you have to represent everything in base 8

I also cant divide DE413F by C in base 10 without rewriting the numbers first

but who would ever ask that

[patent acorn]

regardless of what base you're working in, dividing 4 * 8 + 2 by 4 is just different to dividing forty two (4 * ten + 2) by 4, because those are different numbers

[broken phoenix]

Comp sci subjects 💔

[broken phoenix]

That makes sense

[west glade]

show the original. its probably not phrased like that

phrasing is important

[patent acorn]

and yeah, if you want to do the division while working in base 8 then the first step is to write down the numbers in base 8

[broken phoenix]

I made it up

[west glade]

see

[patent acorn]

which incidentally is the same as how it works in decimal

[west glade]

so your course didnt ask it

[broken phoenix]

Heres a task from the course:

6431634/532 (base 7) divide in full complement

[west glade]

so thats a number already represented in base 7

so no problem with that

[broken phoenix]

But the other guy said 42 is also a number in base 8

But it has 2 different representations

4•10+2 and 4•2•5+2

[west glade]

if you are asked to divide 42 by 4 in base 8 then its very likely that both the 42 and 4 are already in base 8

you are not asked to divide 42 by 4 in base 10 and then to write your result in base 8

[broken phoenix]

Okay so 42 already in base 8 is 4•2•5 + 2

[west glade]

I'll agree that its slightly ambiguous but I seriously hope no one would want the second version

[patent acorn]

to be more explicit: the string "42" represents different numbers depending on which base you read it in

if you read it in base 8, then it means 4 * 8 + 2

if you read it in base ten, then it means 4 * ten + 2

[broken phoenix]

But 8 in base 8 is 10

I see

[patent acorn]

...i mean yeah but "42 means 4 * 10 + 2" is in fact true in every base (or i guess every base > 4, if you only allow the symbols from 0 to b-1) so it's not really a useful thing to say if you're trying to clarify what you're talking about

whereas it's completely unambiguous which number the numeral 8 refers to

but anyway yeah, the point is that probably if someone asks you to "divide 42 by 4 in base 8", "42" and "4" should be read as base 8 numerals

just because the alternative, "please read these strings as being in base ten, convert them to base 8, and then divide them", is... weird

[broken phoenix]

What about this example

[patent acorn]

yeah for the same reasons i would guess that 6431634 and 532 are intended to be read in base 7

[dreamy wraith]

The question is how many integers of "a" exists such that it satisfies a|6k+3 and a|4k+3

after calculating i got to a|3 so a = 1, -1, 3, -3 but if we say k = 1 and a = 3 then a|4k+3 -> 3 | 7 which isn't true, so what's the problem

[kindred fulcrum]

are you asking how many integers a divide 6k+3 and 4k+3 for some k?

[dreamy wraith]

yea

[kindred fulcrum]

and k is fixed?

because otherwise the answer is infinity probably

[dreamy wraith]

it isn't in the question

[kindred fulcrum]

Not every a|3 will work

need to check

[kindred fulcrum]

For a=3, k=3 will work

[dreamy wraith]

so the question isn't correct right ? not enough information

[kindred fulcrum]

No there is enough information

Its just that for every a you are looking for some k

[patent acorn]

i think on the most obvious reading, there isn't enough information that you can give an answer that's just like, "2", or "6", or "11", but you could just answer with something like "5 if k is odd, 12 if k is even"

obviously that's not the actual answer but my point is that, even without knowing what k is, you can say something meaningful about how many integers a satisfy a | (6k+3) and a | (4k+3)

[dreamy wraith]

for some k and a the equation given doesn't statify tho

like a = 3 and k = 1

[kindred fulcrum]

Yeah, but i think the answer asks for how many a there exists a k

[patent acorn]

...no it doesn't

the question doesn't say anything about what the quantifier on k is

[kindred fulcrum]

This is why I interpret it that way. Seems most likely

[patent acorn]

it's plausible that that's what the writer of the question intended but i think it's really a stretch to claim that it's what that text actually says

[kindred fulcrum]

I don't it is much of a stretch

[tidal mica]

lol

[junior swallow]

Does this proof work? Write $a = p_{\alpha_1}^{\epsilon_1} \dots p_{\alpha_n}^{\epsilon_n}$, $b = p_{\beta_1}^{\delta_1}, \dots, p_{\beta_m}^{\delta_m}$. Then
\begin{align*}
g(ab) &= g(p_{\alpha_1}^{\epsilon_1} \dots p_{\alpha_n}^{\epsilon_n}p_{\beta_1}^{\delta_1}, \dots, p_{\beta_m}^{\delta_m}) \
&= \sum_{(\epsilon_1, \dots, \epsilon_n, \delta_1, \dots, \delta_m)} f(p_{\alpha_1}^{\epsilon_1} \dots p_{\alpha_n}^{\epsilon_n}p_{\beta_1}^{\delta_1}, \dots, p_{\beta_m}^{\delta_m}) \
&= \sum_{(\epsilon_1, \dots, \epsilon_n, \delta_1, \dots, \delta_m)} f(p_{\alpha_1}^{\epsilon_1} \dots p_{\alpha_n}^{\epsilon_n})f(p_{\beta_1}^{\delta_1}, \dots, p_{\beta_m}^{\delta_m}) \
&= \sum_{(\epsilon_1, \dots, \epsilon_n)} f(p_{\alpha_1}^{\epsilon_1} \dots p_{\alpha_n}^{\epsilon_n}) \sum_{(\delta_1, \dots, \delta_m)} f(p_{\beta_1}^{\delta_1}, \dots, p_{\beta_m}^{\delta_m}) \
&= g(a) g(b)
\end{align*}
as desired.

[sterile pumice]

okeyokay

[kindred fulcrum]

yep it works

[junior swallow]

Why is this true?

[kindred fulcrum]

e_i = 1 mod m_i

[junior swallow]

Yeah that's what I was thinking too but for some reason I'm struggling to apply it

Nvm I got it

We have m_i | x_0 - b_ie_i + b_i(e_i - 1) since m_i | e_i - 1

[kindred fulcrum]

this is messy

$e_i \equiv 1 \bmod m_i$ so $e_i \cdot b_i \equiv b_i \bmod m_i$

[sterile pumice]

ExpertEsquieESQUIE

[junior swallow]

Yeah but then you have to take the sum over all the congruences to get x_0

[kindred fulcrum]

?

$x_0 = b_i e_i \bmod m_i$

[sterile pumice]

ExpertEsquieESQUIE

[junior swallow]

neither e_i b_i or b_i is equal to x_0

Oh never mind

u right

my b

[dim rapids]

teach me the art of mastering LaTeX 🙏

[junior swallow]

It's very easy really

Just wrap everything with $ and look up signs

that's about it

[kindred fulcrum]

and https://detexify.kirelabs.org/classify.html

[dim rapids]

thank you

[dim rapids]

gotcha. I guess it seems daunting at the beginning, but once you get a hang of it it should be okay

Ty

[kindred schooner]

Are these two questions done correctly? I have no prior background in number theory and I haven’t reached the part about ideal yet I know it has absorptive property but I want to make sure my notion is rigorous

[west glade]

why would you want to phrase this with ideals instead of just using the basic def

the first proof should just state b(...) in aZ if you want to use the absorption

the second one is just... why would you not just put the identity 2k+1=(k+1)^2-k^2 on its own

why put it in sets

[quaint gate]

converting math into set theory makes it more valid
-some 20yo prover some time ago

[kindred schooner]

It’s kinda my habit though using set identities, and I haven’t studied number theory before 😭

You’re right I should change it that way it is more concise

Okay I admit I didn’t read the book and I will also do that 😭😭

[left plume]

this was from a uk entrance exam prep textbook. i hope im not being really stupid but this solution is surely incorrect (consider 3^2x7^6x11^10x17^16 for example)?

[carmine tide]

,w prime factor 3927

[sterile pumice]

Results provided by WolframAlpha

Click here to refine your query online
Upgrade to WolframAlpha Pro!

Requested by civil_service_pigeon

[carmine tide]

,calc 3711*17

[sterile pumice]

Result:

3927

[carmine tide]

yeah solution is defintely wrong without reading it

[hushed sable]

Can you guys help me prove 3 is a primitive root mod 2*7^k for all k?

It’s clearly 3 cause I tabled it in Mathematica for the first bajillion cases so I figure proceed by induction but I’m kind of clueless

[kindred moss]

induction makes sense yeah \

The size of the relatively prime set for mod $2 * 7^k$ is $s_k = 6 * 7^{k-1}$ \

we basically just need to show that $3^{s_k}$ is not 1 mod $2 * 7^{k+1}$. This forces the order to be greater than $s_k$, because the order must divide $s_{k+1}$, and every proper factor of $s_{k+1}$ is a factor of $s_k$. The order is then forced to be maximal. \

by CRT we can simplify this to showing that $3^{s_k}$ is not 1 mod $7^{k+1}$. each $s_k$ stays the same since phi(2) = 1. \

$3^{s_1}$ is not 1 mod $7^2$, so that shows the base case \

Now, if $3^{s_k}$ is not 1 mod $7^{k+1}$, then $3^{s_k} = 1 + c * 7^k$ mod $7^{k+1}$, for c not congruent to 0 mod 7. \

Raise both sides to the 7th power, the binomial expansion results in the RHS being $1 + c * 7^{k+1} + m * 7^{k+2}$ mod $7^{k+1}$, where m is some integer resulting from the higher powers of $7^k$ in the expansion. \

since c is not 0 mod 7, this means that $3^{s_{k+1}}$ is not congruent to 1 mod $7^{k+2}$, and we're done

[sterile pumice]

snowflake

[broken phoenix]

can anybody tell me what is the algorithm for solving tasks like calculating the remainder of $11^{33^{55}}$ when dividing by 41? I know Euler's function is used to simplify it but I don't fully understand the process

[sterile pumice]

danilojonic

[carmine tide]

Here, we're working mod 41, so it's natural to take n=41

as a sanity check, we can confirm that gcd(11,41), so the theorem applies

$41$ is prime $\implies \phi(41)=40 \implies 11^{40} \equiv 1 \pmod{41}$

[sterile pumice]

Civil Service Pigeon

[carmine tide]

this is the euler's stuff you were talking about, right?

if so, do you follow?

[broken phoenix]

yeah

[broken phoenix]

correct

but I don't know what to do after that step

[carmine tide]

would you agree that $11^{40k} \equiv 1 \pmod{41}$ for all integers $k$?

[sterile pumice]

Civil Service Pigeon

[broken phoenix]

yes

[carmine tide]

and so would you agree that $$11^r \equiv 11^{r \pmod{40}} \pmod{41}?$$

[sterile pumice]

Civil Service Pigeon

[carmine tide]

@broken phoenix Hello?

[torn kindle]

If the number of divisors of the gcd of two numbers can be considered the number of common divisors of two numbers, what would d(lcm(a,b)) be?

Furthermore, this computes to $\prod_{1}^{k}{[min(a_i, b_i) + 1]}$ and $\prod_{1}^{k|k-l|}{[max(a_i, b_i) + 1]}$ , where l is the number of primes in the prime factorization of b and k respectively for a.

[broken phoenix]

Sorry I was distracted had something to do I'm back now

[broken phoenix]

It's kind of weird to wrap it like that I don't quite understand the r (mod 40) part

[sterile pumice]

DeRainMan

[carmine tide]

Suppose that we let $r=40a+b$ for integers $a$ and $b$ where $0 \leq b \leq 39$. Do you agree that $$11^r=11^{40a+b}=11^{40a} \cdot 11^b?$$

[sterile pumice]

Civil Service Pigeon

[carmine tide]

I'm assuming you're letting the prime factorisations of $a$ and $b$ be $a=\prod^{k}{i=1} p_i^{a_i}$ and $b=\prod^{k}{i=1} p_i^{b_i}$.

You are correct that the number of divisors of $\gcd(a,b)$ is $\prod^{k}_{i=1} [\min(a_i, b_i)+1]$.

I'm not sure what's going on with the product $\prod^{k|k-l|}_{i=1} [\max(a_i, b_i)+1]$. If you meant for this to be the number of divisors of $\text{lcm}(a,b)$, then take $a=12$ and $b=18$. Then, as per your definition, $k=l=2$, so the upper limit of your product doesn't make sense (since it is zero, which is less than the lower limit of one).

[sterile pumice]

Civil Service Pigeon

[carmine tide]

@broken phoenix you here?

[broken phoenix]

Yeah

Reading

[broken phoenix]

Yes it makes sense

[carmine tide]

mhm

so $11^{40a} \equiv 1 \pmod{41} \implies 11^{40a} \cdot 11^b \cdot 11^b \pmod{41}$

[sterile pumice]

Civil Service Pigeon

[carmine tide]

and you should notice that $b$ is just $r \pmod{40}$

[sterile pumice]

Civil Service Pigeon

[carmine tide]

which is where this came from

[broken phoenix]

Hmm

[broken phoenix]

This implication I didn't understand

[carmine tide]

that's because I typo'ed

[broken phoenix]

The left part makes sense but the conclusion doesn't

[carmine tide]

so $11^{40a} \equiv 1 \pmod{41} \implies 11^{40a} \cdot 11^b \equiv 11^b \pmod{41}$

[sterile pumice]

Civil Service Pigeon

[carmine tide]

there we go

[broken phoenix]

Okay yeah that makes sense

And b is r okay got that

[carmine tide]

mhm

[carmine tide]

So we now have $$11^{33^{55}} \equiv 11^{33^{55} \pmod{40}} \pmod{41}$$

[sterile pumice]

Civil Service Pigeon

[carmine tide]

so we can turn our attention to calculating $33^{55} \pmod{40}$

[sterile pumice]

Civil Service Pigeon

[carmine tide]

can you do that?

[broken phoenix]

We repeat euler again?

*first time it was special version of euler because 41 was prime

[carmine tide]

mhm

[broken phoenix]

I got to $55 \equiv 1$ (mod 16)

[sterile pumice]

danilojonic

[carmine tide]

,w phi(40)

[sterile pumice]

Results provided by WolframAlpha

Click here to refine your query online
Upgrade to WolframAlpha Pro!

Requested by civil_service_pigeon

[carmine tide]

what

,w 55 mod 16

[sterile pumice]

Results provided by WolframAlpha

Click here to refine your query online
Upgrade to WolframAlpha Pro!

Requested by civil_service_pigeon

[carmine tide]

(also I'm leaving in 5 minutes)

[broken phoenix]

That's fine, I know how to use the Euler function but the rest of the steps don't make sense ☠️

[carmine tide]

where did this come from?

did you just calculate wrong

[broken phoenix]

So I basically replicated the first step

[carmine tide]

how did you calculate 55 is 1 mod 16****

[broken phoenix]

$33^{16} \equiv 33^{55 \pmod{16}} \pmod{40}$

[sterile pumice]

danilojonic

[carmine tide]

@broken phoenix My point here was that you should’ve ended up with $33^7$, not $33^1$.
$$33^7 \equiv (-7)^7 \equiv -49^3 \cdot 7 \equiv -7 \cdot 9^3 \pmod{40}$$ which is bashable.

[sterile pumice]

Civil Service Pigeon

[torn kindle]

Sorry, typo, it is meant to be k + |k - l|, it accounts for if b's number of prime factors is bigger than a's. The prime factorization is from 1 to l for b and 1 to k for a. If a is larger than b, then it can overshoot, but it still evaluates to the same number. Although this is not the case if you combine both of the prods to get ${a_i}{b_i}$ + ${a_i}$ + ${b_i}$ + 1, in which case the upper-bound would have to be exact, but im not sure as to what value, presumably the number of prime factors of the bigger of the two.

[sterile pumice]

DeRainMan

[torn kindle]

In hindsight, max(l, k) works

[torn kindle]

Also, I would like to talk about finding a formula for d(n!). I just combined it lengendre's formula and it seems to compute accurately, got 255530 divisors for 24!

[torn kindle]

Is there an alternative to tau(n)/d(n)? One that does not require prime factorization

[junior swallow]

May I please have a hint for 11

[kindred fulcrum]

You have a big hint already in the question

were you able to prove that \mu(d)/d is multiplicitive?

[junior swallow]

Yes

[kindred fulcrum]

then by q10, the sum over the divisors is multiplicitive

also, phi(n) and n are multiplicative

so by 9 you only need to show equality of phi(n) and the RHS on prime powers

[junior swallow]

Why do we care about n being multiplicative

Is the product of multiplicative functions multiplicative?

[kindred fulcrum]

because then both sides are multplicative

[kindred fulcrum]

ofc

[junior swallow]

I get that we want to show that both sides are multiplicative

[kindred fulcrum]

@junior swallow need any more help?

[junior swallow]

No I got it, ty

[broken phoenix]

I don't know what I'm doing. I was trying to replicate the process because I couldn't understand it. Mind explaining the steps in detail?

Can we take an example what are the last two digits of: $123^{456^{789}}$?

So this tells me what is the remainder $(mod 100)$

[sterile pumice]

danilojonic

[kindred fulcrum]

First, you can see 123 is equivalent to 23 mod 100

Second, gcd(23,100)=1 so we can use euler's theorem.

Then we reduce the exponent 456^789 modulo phi(100)=40

[broken phoenix]

that's the part I am most interested about

[broken phoenix]

this is confusing. Yes, 123 is equivalent to 23 mod 100 but we have 123^x which gives a huge result.

[kindred fulcrum]

to find 456 ^ 789 mod 40 we repeat the argument

[broken phoenix]

456 mod 40?

[kindred fulcrum]

456 ^ 789 mod 40

[broken phoenix]

but here you ignored the power

[kindred fulcrum]

yeah because (ab) mod n = ((a mod n)(b mod n)) mod n

[fading herald]

Are you a first year ?

[junior swallow]

Nah bro I graduated 😂

Damn😹😹

Bros ruthless

[fading herald]

So is this like a place for me ?

I mean I'm a first year and I don't udnerstand what you guys are talking about

[broken phoenix]

number theory is generally not done in first year I think

you should be doing analysis, linear algebra, math logic / intro to proofs etc.

[fading herald]

Is the early university region even for me ?

[broken phoenix]

ofc yes, it depends on your subjects tho. Wherever you see a familiar subject name that's the channel for it #calculus #linear-algebra #proofs-and-logic #discrete-math

even though groups are categorized as advanced math im doing them in 2nd year so it doesn't really matter what channel you use as long as it's on topic

[fading herald]

I see I'm stil trying to do lots of things like physics and maths and everywhere I go I can't contribute it seems I am always below everyone

[broken phoenix]

just ignore what they're doing and focus on your own problem

not everyone is on the same level and that's perfectly normal

[fading herald]

But my problem is to be of help to others by solving questions and contributing I wish I could be like you and others I'm trying to study hard ofc but it seems it's not helping

I don't think we should talk about these thing here is there an off-topic region

Can we use #discussion

[kindred fulcrum]

groups being done in 2nd year is pretty normal

[broken phoenix]

I ain't helping nobody here, I am the one recieving help all the time 😭 🙏

[kindred fulcrum]

its perfectly fine to recieve help 🙂

[torn kindle]

Is there anything related to Legendre's Formula for factoring factorials or subjects across fields?

[fading herald]

Damn we are same then ?

[junior swallow]

May I please have a hint on a? So far, I have the following (I feel I am overcomplicating things):

If $n = p_1^{\epsilon_1} \dots p_m^{\epsilon_m}$, we have
\begin{align*}
\sum_{d \mid n} \mu(n/d) \nu(d) &= \sum_{0 \leq \delta_i \leq \epsilon_i} \mu(p_1^{\epsilon_1 - \delta_1} \dots p_n^{\epsilon_n - \delta_n}) \nu(p_1^{\delta_1} \dots p_n^{\delta_n}) \
&= \sum_{\epsilon_i - 1 \leq \delta_i \leq \epsilon_i} \mu(p_1^{\epsilon_1 - \delta_1} \dots p_n^{\epsilon_n - \delta_n}) \nu(p_1^{\delta_1} \dots p_n^{\delta_n})
\end{align*}

[sterile pumice]

okeyokay

[kindred fulcrum]

What is mu?

[junior swallow]

The Mobius u function

u(1) = 1, u(n) = 0 if n is not square free, and u(p_1 \dots p_n) = (-1)^n where the p_n are distinct positive primes

[kindred fulcrum]

I meant nu

Sorry

[junior swallow]

Oh

v(n) = number of positive divisors of n

There's a closed from expression for \nu given in the book

[kindred fulcrum]

Do you know mobius inversion?

[junior swallow]

Yeah, it looks very applicable here and I want to take \nu(n/d) = F(n/d)

Oh wait is it just that v(n) = \sum_{d \mid n} 1 lol

[kindred fulcrum]

Yep

[junior swallow]

Lol ok

[tall arch]

Just use dirichlet convolution right?

[junior swallow]

Ye I got it

[tall arch]

Since v(n) and möbius are both multiplicative functions, the dirichlet convolution of them is also multiplicative

So u can split into prime powers

Oops

It’s alr above

[red yacht]

Find the smallest $n \in \mathbb{N}$ such that $(5n^2 : 2^2 \cdot 3^4 \cdot 5 \cdot 7)=45$ and that has exactly $12$ positive divisors.

[sterile pumice]

Renato

[red yacht]

can i get help

[modest coral]

( : ) is gcd?

i think (ax : ay) = a (x : y)

[unique cypress]

weird notation

[red yacht]

yeah

[red yacht]

yeah

[red yacht]

5gcd(n^2, 2^2.3^4.7)=5.9

[modest coral]

then || the power of 3 in n is 1,|| and || 2,5,7 don't divide n ||

[red yacht]

hold on

3^2=gcd(n^2, 2^2 . 3^4 . 7)

[modest coral]

yeah

[red yacht]

yeah i guess you can say 2 and 7 don't divide n

3^2=gcd(n^2, 3^4 ) so this?

[modest coral]

no

oh

maybe

[red yacht]

i mean if the result of the gcd does not have any factors of 2 or 7, then yeah n does not divide 2 nor 7

[red yacht]

since n does not divide 14 then it's equivalent to the last gcd i sent i think

[modest coral]

anyway do you know the number of factors is the product of 1+r for each power r in the prime factorization?

[red yacht]

yes

12 = (1+x1)(1+x2)(1+x3)...

[modest coral]

you can take it by cases, n has 1 or 2 or 3 or 4 prime factors...
if it has 4 or more prime factors then it will have more than 12 factors, so that's impossible

so just 3 cases

1 prime factor is also impossible because then n=3 which only has 2 factors, which is less than 12

so 2 cases

[red yacht]

2^(x1) . 3^(x2) . 5^(x3) . 7^(x4) . 11^(x5) . ...

but we know x1=x4=0

[modest coral]

x3 = 0 as well

and x2 = 1

oh sorry, x3 doesn't have to be 0, my mistake

<@&268886789983436800>

[red yacht]

i edited the message

[red yacht]

this has to be equal to 9?

[modest coral]

no

[red yacht]

45

[modest coral]

the gcd condition will be satisfied iff x2 = 1 and x1 = x4 = 0

[red yacht]

why is 3^1?

what happens if 3^2

[modest coral]

then gcd(n^2, 2^2 . 3^4 . 7) is too big

[red yacht]

this is equal to 45?

[modest coral]

how?

[red yacht]

this prime factorization, do we need to equal it to something?

[modest coral]

no, take it by cases. n has either 2 or 3 prime factors

[red yacht]

for example here this product of the exponents is the number of positive divisors

[modest coral]

yeah

12 = 2 (1+x3) (1+x5) (1+x6) (1+x7)...

[red yacht]

wait but, we know N it's not divisible by 14

[modest coral]

^

[red yacht]

if x2=1, then gcd is too big?

[modest coral]

if x2 > 1 then gcd is too big

if x2 > 1 then the gcd will have 3^4

[modest coral]

but the gcd is only 9

[red yacht]

for example if n divides 9

[modest coral]

if 9 divides n

[red yacht]

if 9 divides n

then 81 divides n^2 sort of logic?

[modest coral]

yes 81 divides n^2, and also 81 divides 2^2 . 3^4 . 7
so 81 divides gcd(n^2, 2^2 . 3^4 . 7), which equals 3^2
so 81 divides 9, a contradiction

[red yacht]

yeah great

so $2^0 \times 3^1 \times 5^? \times 7^0 \times 11^{??} \times \cdots$

[sterile pumice]

Renato

[modest coral]

💯

[red yacht]

12 = (0+1)(1+1)(x+1)(0+1)(y+1)...

12 = 2(x+1)(y+1)...

[modest coral]

let's use x_5, x_11, x_13...

for the variables

[red yacht]

yeah

12 = (0+1)(1+1)(x5+1)(0+1)(x11+1)...

12 = 2(x5+1)(x11+1)...

[modest coral]

wait

[red yacht]

srysry

[modest coral]

12 = (0+1)(1+1)(x5+1)(0+1)(x11+1)...

yeah

[red yacht]

6 = (x5+1)(x11+1)

x5 = 2 and x11 = 1

[modest coral]

sure, you threw away the primes bigger than 11, but that should be ok

[red yacht]

yeah

we trying to minimize

[modest coral]

yeah that's the answer i got

[red yacht]

,calc 32511

[sterile pumice]

Result:

825

[modest coral]

3 . 5^5 is also a solution but it's bigger

[red yacht]

yeah

,calc 3511^2

[sterile pumice]

Result:

1815

[red yacht]

i appreciate the help

[modest coral]

np

[molten kiln]

\Large\textbf{My Problem}\
\normalsize
Let (p) be a prime with (p\equiv 1 \pmod{4}).
Does there always exist a positive integer (a) and a divisor (d\mid a^{2}) such that
[pd\equiv-a\pmod{4a-1}]

\Large\textbf{My Work}\
\normalsize
If one takes the “trivial” choices (d\in{1,a,a^2}), then the congruence reduces to the conditions [4p+1,\quad p+1,\quad p+4] each having a divisor (q\equiv 3 \pmod{4}). So, whenever one of these three numbers has such a divisor, the congruence is solved.\

However, each of (4p+1,; p+1,; p+4) can itself be a prime congruent to (1\pmod{4}). (Dirichlet can gaurantee this happens). In those cases, none of the trivial choices for (d) will succeed.\

Moreover, nontrivial divisors (d) are possible. For example, if (a=6) then (d=2) is allowed, and in principle this can lead to additional solutions. For example, if (p=70009) then indeed one may verify (2\cdot70009+6\equiv0\pmod{4\cdot6-1}).\

In general, I have shown that any valid divisor must take the canonical form [d=rs^2]where (r,s\mid a) and (r) is squarefree. The proof is straightforward from unique prime factorization and I omit it here, but this representation is always possible. In the trivial cases this is the same as ((r,s)=(1,1),(a,1),(1,a)).\

Finally, I have written code to test this up to (10^8) and it appears to hold, but if heuristics were enough for a proof much smarter people than I would have solved much harder problems...\

\Large\textbf{My Question}\
\normalsize
Where I am stuck: how can one prove that for every prime (p\equiv 1\pmod{4}), there exists some (a) and some divisor (d\mid a^{2}) satisfying the congruence
[pd\equiv-a\pmod{4a-1}]
Or, equivalently if my idea is any good, how can one prove that the families of solutions obtained from (d=rs^2) always cover all such primes (p)?
Any ideas from other people would be greatly appreciated.

[sterile pumice]

PajamaMamaLlama

[molten kiln]

I posted this in the help channels and a few people told me to come here for help with answer, so idk if I can just post this ouright but lemme know

oh and if respond please ping

[red yacht]

Let $a \in \mbb{Z}$ such that neither $3$ or $7$ divide $a^2 - 1$. \ Show that $3^3 \cdot 7$ divides $a^2(a^2+3)(a^2 + 5)$

hey. Can i get some help?

[tall arch]

how tf does 1 not divide a^2-1 💀 💀

is it meant to be 3?

@red yacht

[sterile pumice]

Renato

[tall arch]

alr

so if a^2 -1 is not 0 (mod 3)

a^2 is NOT. 1 mod 3

this only happens if a =0 (mod 3)

as a =1,2(mod 3) --> a^2 = 1 (mod 3)

thus, we have 3|a

additionaly, a^2 ≠ 1 (mod 7)

and QR of a mod 7 is 0,1,4,2,2,4,1

so a^2 = 0,2,4 (mod 7)

and since 3|a, a^2 = 0 (mod 9)

therefore, 27|a^2(a^2+3)(a^2+5)

as 9|a^2 and 3|(a^2+3)

addiiotnally, if a^2 = 0,2, or 4 (mod 7), then 7|a^2(a^2+3)(a^2+5)

so 3^3*7|a^2(a^2+3)(a^2+5)

[wooden glen]

I think you're done here, since then either a² or a²+3 or a³+5 is 0 (mod 7).

Anyway,

[kindred fulcrum]

#help-48

[wooden glen]

!nosols

[rotund gust]

As a helper, please do not give out answers that could be copied as a homework solution. Have the student work through the problem themselves and guide them along the way.

[hoary shell]

Let a,b be rationals and d square free. Is there an easy way to see why 2a in Z and a^2 - b^2 d in Z iff 2a in Z and 2b in Z?

I took an embarrassingly long time to figure it out

[charred roost]

Hnm, is that actually true? Let a = 1 and b = 1/2 and d = 1, then 2a and 2b are in Z, but a^2 - b^2 d = 3/4 isn't

[tulip vortex]

Don't you also need d to be congruent to 3 mod 4 ?

[unique cypress]

I'm trying to guess the context of this

a^2-b^2 d reminds me of the norm of quadratic fields

Are you trying to classify the ring of integers?

[hoary shell]

yes I am

I know the answer I'm just trying to make sense why the mod 4 argument appears

Trying to explain it to somebody

For d=1 mod 4, the ring is larger than Z[sqrt(d)]

[unique cypress]

[hoary shell]

This pissed me off so I went to try stuff down and I got it now

[wise karma]

I'm tryna do a research project for a high school science fair. I want to study something in ENT. Any suggestions?

[kindred fulcrum]

Quadratic Reciprocity

[junior swallow]

Could I have a hint for this please

[west glade]

v(n) is what?

[junior swallow]

Number of positive divisors of n

I was thinking that since we have a closed form expression for v(n) we just distribute that out

[west glade]

square both sides

[junior swallow]

Ye I've done that

[west glade]

pair up the numbers on the left

then you're done

[modest coral]

Is there notation for "the power of p in n"?

[junior swallow]

Pretty sure it's just ord_p(n)?

[modest coral]

I.e. the largest natural number m such that p^m divides n

But I thought "order" was a minimal power, not maximal

[junior swallow]

Nah it's maximal

[modest coral]

I guess "order" has two meanings then

I'm thinking of groups

[kindred fulcrum]

minimal would be m=0

[modest coral]

0 doesn't count

[kindred fulcrum]

so 1

its still doesn't make sense to make that a definition

[west glade]

also called p-adic valuation

also often denoted v_p(n)

[modest coral]

V for valuation?

Or is that like a nu or something

[kindred fulcrum]

v

[kindred fulcrum]

Probably

[lilac bronze]

-# it measures the p-ness of a number

[junior swallow]

If $n = p_1^{a_1} \dots p_l^{a_l}$, then the LHS (after squaring) is $\prod_{b_i \leq a_i} p_1^{2 b_1} \dots p_l^{2 b_l}$. The RHS is $(p_1^{a_1} \dots p_l^{a_l})^{(a_1 + 1) \dots (a_l + l)}$. It suffices to show that $p_i^{a_i (a_1 + 1) \dots (a_l + 1)} = p_i^{2 \sum_{j = 0}^{a_i} j$, aka $a_i (a_1 + 1) \dots (a_l + 1) = 2 \sum_{j = 0}^{a_i} j$?

[modest coral]

I think you have to reverse one of the lists when you pair them up

[sterile pumice]

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

[west glade]

I did not say to consider the prime factorization

you do not have to do that

do an example for n=10

pair up the numbers on the left so that you have the factor 10 four times

[kindred fulcrum]

if d is a divisor then n/d is also a divisor

[tidal ravine]

I have seen the notation $a^k \mid\mid b$ used in some old books to denote that $a^k \mid b$ but $a^{k + 1} \nmid b$.

[modest coral]

i was confused because nu was used in the problem okeyokay posted

but i guess it doesn't have a subscript there

[west glade]

number theory notation isnt exactly consistent over time

the divisor function is also often called d(n) or sigma_0(n) or tau(n)

[junior swallow]

If $n = p_1^{\epsilon_1} \dots p_n^{\epsilon_n}$, isn't $\sum_{d \mid n} \wedge (d) = \sum_{1 \leq i \leq n} \log p_i$?

[sterile pumice]

okeyokay

[versed flax]

try n=p^k where p is a prime and k>1

does \sum Λ(d)=log p hold in this case?

[west glade]

and a sum of logs is what?

you also forgot to consider how often each term appears

[kindred fulcrum]

why delete

[junior swallow]

Can somebody check my answer for showing that there are infinitely many primes congruent to -1 modulo 6? Suppose that there are only $m$ primes of the form $6k - 1$. Set $N = 6p_1 p_2 \dots p_m - 1$. An integer divided by 6 leaves a remainder of $-1, 0, 1, 2, 3$, or 4. Now
\begin{align*}
(6k + 1)(6k' + 1) &= 6(6kk' + k + k') + 1 \
(6k + 3)(6k' + 3) &= 6(6kk' + 3k + 3k' + 1) + 3 \
(6k + 3)(6k' + 1) &= 6(6kk' + 3k + k') + 3
\end{align*}
Therefore any integer of the form $6k - 1$ must be divisible by a prime of the form $6k - 1$. Now, $N$ is not divisible by any of the $p_i$, but must be divisible by a prime $p$ of the form $6k - 1$. We have $p > p_m$, which is a contradiction.

[sterile pumice]

okeyokay

[carmine tide]

saying that the remainders are -1, 0, 1, 2, 3, or 4 is abusive

[https://en.wikipedia.org/wiki/Remainder]

[carmine tide]

maybe make your exhaustion logic for the "therefore any integer of the form 6k-1 ust be divisible by a prime of the form 6k-1" a little more explicit

also at the end you say $p>p_m$, but never make an explicit statement about size, so I'd include that too

[sterile pumice]

Civil Service Pigeon

[kindred fulcrum]

I don't evem understand what is the argument to get this result

2 and 3 don't divide N. And any other prime is +-1 mod 6.

So if N is not divisable by a prime -1 mod 6 it must be 1 mod 6.

[carmine tide]

I think their idea was to exclude the even numbers out of 6k, 6k+1, ... 6k+5, then show that if you only have factors of 6k+1 and 6k+3, then you can't get 6k-1 (obviously this can be more flesched out since they only explicitly write it for two factors, though the generalisation is trivial), so there must be a factor of 6k-1 by exhaustion or smt like that

[junior swallow]

Yeah I just mimicked the proof in Ireland Rosen

[junior swallow]

Could I have a hint for this problem? Since this is a chapter on congruences, I thought about reducing both sides mod 2

There is also a proposition which lists criteria for the solvability of the congruence ax \equiv b (m), the only problem being here that it doesn't deal with quadratic parameters

I was thinking about considering the congruence 3x^2 = y^2 (2), then setting s = x^2, t = y^2, so that we get 3s = t (2), but that didn't lead anywhere lmao

I've also considered cases where x is even, y is even, x is odd, y is even, etc. and found that both must be either even or odd

[rugged locust]

turns out 2 is too small a number to work with for diophantine equations, and it isn't really that useful most of the times

try mod 3

[junior swallow]

Ok so then we get y^2 \equiv 2 mod 3...

hm..

Is the point that there are no elements of Z_3 such that y^2 = 2?

Wait am I tripping

Oh nah okay

thanks

Is this a good strategy in general

To reduce via low moduluses and then manually check all the solutions

like for example if we're working with Z_n where n is small it's not that tedious

[rugged locust]

well turns out there is this thing called quardratic reciprocity

and it actually gives a really efficient algorithm for determining of x^2 = a mod n has solutions or not

but yes at this level it's just checking cases

[junior swallow]

oh cool

If I'm not mistaken, doesn't setting x= 0 show that -1 \equiv -(p - 1)! (p)?

[rugged locust]

where's the extra -1 coming from

[junior swallow]

$(-1) (-2) \dots (- (p - 1)) = (-1)^{p - 1} (p - 1)! = -(p - 1)!$

[sterile pumice]

okeyokay

[junior swallow]

or am I trippin

wait nvm

I'm dumb

prime - 1 = even

[rugged locust]

p=2 can be checked separately yeah

[junior swallow]

Should this be the left hand side instead?

Also, can somebody please explain to me why the sentence before the highlighted one implies the highlighted one?

Does this have to do with Lagrange or something like that I lowkey forget group theory

[modest coral]

yeah if an element is in that subgroup, then its order must divide d. conversely if its order divides d, then it satisfies x^d = 1, so it's in that subgroup

so the subgroup is equal to the set of elements with order dividing d

you can count the size of this set by partitioning it based on the order of the elements

on one hand, the size is the order of the subgroup, d
on the other hand, the size is the sum of the sizes of the cells in the partition

if an element is in that subgroup, then its order must divide d
this follows from lagrange, like you said

[sacred junco]

Is the sum of all n^k from 1 to n equal to (n)×((1)×(n+1)×...×(kn+1))/(k+1)!

So n(n+1)(2n+1)(3n+1)(4n+1)/5! for i^4 where i=1...n

[kindred fulcrum]

No

[kindred fulcrum]

5! Is divisable by 8 while the numerator is usually not

n=2 for example

Also for i^3 the formula is known as
n^2 * (n+1)^2 / 4

[sacred junco]

Is this just the sum for i squared

[kindred fulcrum]

Sum for i^1 squared

[sacred junco]

Whoops

[sacred junco]

can this be generalized?

[kindred fulcrum]

https://en.m.wikipedia.org/wiki/Faulhaber's_formula

The pattern of squaring doesn't repeat

But there are some other patterns

[round elbow]

Hi everyone! 👋
I’m a Class X student from India, and I’ve developed a number-theory conjecture
called “The Kalita Picky-Partner Prime Conjecture.”

It studies selective and symmetric relationships between primes using domain-based linear forms.
I’d really appreciate any thoughts or feedback from the community!

Here’s my PDF:

[west glade]

!nopdf

[rotund gust]

Please post images (such as PNGs or JPGs) of the question rather than other filetypes such as PDFs which have to be downloaded. Non-image downloads can potentially contain viruses or other security risks.

[west glade]

It studies selective and symmetric relationships between primes using domain-based linear forms.
that sentence really manages to say nothing. be more specific

[rare yacht]

Does anyone have tips or like advice on learning elementary number theory( like eg where)?I just got into uni and id like to prepare in advance. Thanks!!

[junior swallow]

Does this proof work for 7? Since $a_i^{\phi(n)} \equiv 1 ; \text{mod } n$, $(a a_i)^{\phi(n)} \equiv 1 ; \text{mod } n$, we have
[\overline{a_i}^{\phi(n)} = \overline{a}^{\phi(n)} \overline{a_i}^{\phi(n)} \in \mathbb{Z}_n] Therefore $\overline{a}^{\phi(n)} = \overline{1}$, which is to say that $a^{\phi(n)} \equiv 1 ; \text{mod }n$.

[sterile pumice]

okeyokay

[kindred fulcrum]

Why is a_i^phi(n) = 1 mod n

[rich steppe]

Hi could someone here please check my post (not a mathematician here) are any of the steps taken here valid? If so how could this be pushed further?

https://www.reddit.com/r/Collatz/comments/1nzmui4/are_any_of_the_steps_valid_if_so_how_could_this/

[junior swallow]

My idea was that there are exactly \phi(n) units in Z_n, and all of the a_i are units, and there are \phi(n) of them, so they must all be exactly the units in Z_N

[kindred fulcrum]

can't you prove this way the theorem without 6?

[junior swallow]

Well I used 6 when I said that (a a_i)^{\phi(n)} = 1 in Z_n

Also pairwise incongruent modulo n means that the elements are all distinct in Z_n

[kindred fulcrum]

ok, isn't this the same as the group theory proof?

a^k ranges over all of the units in Zn

so it must be 1 eventually

by pigeonhole it must be after at most phi(n) steps

[rich steppe]

anyone?

[junior swallow]

Got it, I wonder if I should review Lagrange lol

[modest coral]

the order of a subgroup divides the order of the group

the order of an element is the order of the cyclic subgroup generated by that element

[junior swallow]

So what you said is: Suppose that x is an element of order c, where c | d. Then ck = d, so that x^{ck} = (x^c)^k = 1^k = 1. Therefore, any element of order which divides d has order d. Conversely, any element with order d has order which divides d; namely, d itself

Wait hold up I'm wrong right, the order is the least number k such that x^k = 1

[modest coral]

any element of order which divides d has order d
any element of order which divides d satisfies x^d = 1

the order is the least number k such that x^k = 1
yes

[junior swallow]

So how is an element with order k < d where k | d have order d

[modest coral]

it doesn't

[junior swallow]

Ohh I think I get it now.

If we take all elements in the group and generate their cyclic group, they will have some order

and this order must divide d, by lagrange

[modest coral]

that's part of it

we want to show that an element satisfies x^d = 1 if and only if its order divides d

[junior swallow]

<= is clear

[modest coral]

yeah

[junior swallow]

Well, if x^d = 1, then it's an element of the subgroup of elements satisfying x^d = 1 lol

We can generate its cyclic subgroup

the order of this subgroup must divide d

[modest coral]

yeah exactly

[junior swallow]

but the order of this subgroup is simply the order of x

[modest coral]

yes

[junior swallow]

okay got it ty

Am I going insane? If p = 3, then phi(p - 1) = phi(2) = 1, no?

did they mean greater than or equal to 1?

All we need is one element in order to generate the group

[modest coral]

That's weird

[rugged locust]

why would it be equal to 1

[modest coral]

It's as they said, phi(3-1)=1

phi(p) = p-1 for primes p

But yeah it seems like you only need >= 1

[modest coral]

Actually, I think we can still say

x satisfies x^d=1 iff the order of x divides d
Even if we don't know how many elements satisfy x^d=1

I think that might rely on the division algorithm rather than Lagrange

[icy epoch]

If a != b and n is natural then (a-b)|(a^n - b^n).

Can someone give me a small hint on this one

[west glade]

do you know the formulas for a^2-b^2 and a^3-b^3? try generalizing them

[icy epoch]

Does it then separate into two cases where n is either even or odd

[west glade]

no

[signal veldt]

Alternatively, this is also a consequence of the factor theorem for polynomials.

[west glade]

or as another alternative, this is the geometric sum in disguise

[sacred junco]

write a = (a - b) + b on RHS

[slim vortex]

you can also verify it with polynomial long division

[junior swallow]

Could I have a hint for using 12 to prove 13

[junior swallow]

What is ur pfp

[versed flax]

hint: ||start with induction on a and then use 12 in the inductive step||

ah you can use this argument to prove fermat's little theorem for any a, and then reach the desired result for (a,p)=1 from them there

but note that by fermat's little theorem i dont exactly mean a^{p-1}\equiv 1 mod p because this isnt true for p|a

instead i mean the slightly different version which is a^p\equiv a mod p

[junior swallow]

Ohh ok I think I got it thanks

Does this not follow from the fact that Zn is isomorphic to the direct sum of Z_{p_i^{a_i}}?

For f(a) = 0 in Z_n if and only if f(a) = 0 in all the Z_{p_i^{a_i}}

[kindred fulcrum]

yeah this is a consequence of CRT

[mighty cove]

so for the order 3 magic square all 8 possible magic series are encoded in it. All 8 possible partitions of 15 with exactly 3 distinct parts, all less than or equal to 9. Which are encoded in the 3 columns + 3 rows + 2 diagonals.

For order 4 magic squares there are 86 possible magic series, or partitions of 34 with exactly 4 distinct parts, all less than or equal to 16. But how would they all be encoded in a 4 by 4 magic square appropriately?

There are 1820 many ways to sum 4 cells in a 4 by 4 square, and each of those could be one of the 86 possible order 4 magic series. Here's a visual of 252 of them, reduced by dihedral symmetry for brevity.

[junior swallow]

Could I have a hint for this problem? So far, I have assumed that $k$ is a solution, so that $p^a \mid (k - 1) (k + 1) = k^2 - 1$. Thus, $p \mid (k - 1)$ or $p \mid (k + 1)$.

[sterile pumice]

okeyokay

[kindred moss]

specifically, p^a must divide one or the other, since p can't divide both (or else p = 2)

[unkempt fossil]

Can someone help:
Find all integers a, b, q with q >=3 and q odd st.
a^q(a^q - 4) = 8(b^q - 1)

[carmine tide]

In the future, please show what you’ve done so far when asking for help - it gives us more context of where to help you (and saves our time from explaining things unnecessarily). \ \

It’s easy to see that $a^q$ must be divisible by $8$. So, if we let $y=a^q-2$, then
$$y^2+4=8b^q$$
and since $y$ is even, letting $y=2z$ yields
$$4z^2+4=8b^q \implies z^2+1=2b^q$$
Clearly, both $z$ and $b$ are odd. From here, consider working in $\mathbb{Z}[i]$.

[sterile pumice]

Civil Service Pigeon

[carmine tide]

Unless you already have the result for x^2+1=2y^n memorised, in which case

[wicked roost]

can anyone explain recurrently defined gcd?

the formula goes like gcd(a, b) = gcd(b, a%b)

but i dont understand it

[carmine tide]

https://math.stackexchange.com/questions/95799/why-gcdb-qbr-gcdb-r-so-gcdb-a-gcdb-a-bmod-b

[unkempt fossil]

Is there any way to avoid Gaussian integers?

[kindred fulcrum]

probably quadratic residues

[zealous thorn]

Lol

[junior swallow]

Thanks

[junior swallow]

Can somebody help me see this? Let $\alpha = a + bi$. Since $\mathbb{Z}[i]$ is an Euclidean domain, there is $\beta$, $\gamma = c + di \in \mathbb{Z}[i]$ with $\alpha = \beta (1 + i) + \gamma$. Since $\lambda(\gamma) = c^2 + d^2 < \lambda(1 + i) = 2$, we must have $\lambda(\gamma) = 1$ or $\lambda(\gamma) = 0$. However, we could have $\gamma = i, -i$.

[sterile pumice]

okeyokay

[west glade]

quotient and remainder arent unique in Z[i], are they? so presumably you can choose a different beta which then has gamma in {0,1}

some examples probably help

[junior swallow]

Ahh okay I see

I'll try that ty

[junior swallow]

Can somebody help me see why this is true? I would understand if the exponents were distinct but they're always the same, right?

Like for instance, if t = 2, and the order of g_1 is n_1 and the order of g_2 is n_2, then (g_1 g_2)^i for 0 <= i <= n_1 is n_1 elements, and from then on we get n_2 - n_1 elements (assuming n_1 < n_2), so in total we get n_1 + (n_2 - n_1) = n_2 elements?

[kindred fulcrum]

the order of g is lcm(ord(g1),ord(g2))=lcm(n1,n2)

and the lcm of prime powers (the orders of g_i per the previous line are q_i^e_i) is just their product

@junior swallow just to make sure you notice this

[red yacht]

can I get some help

i need to find all pairs (a,b)

[kindred fulcrum]

Can you find one pair?

[red yacht]

help

[red yacht]

7x3-11

21-11=10

(a,b)=(3,1)

@kindred fulcrum

[kindred fulcrum]

Yeah so how can you find more pairs?

[red yacht]

but i did it out of brute force dude

this is not good

[kindred fulcrum]

Well there is an algorithm

Euclidean Algorithm

[red yacht]

care to elaborate how does it relate

[kindred fulcrum]

do you know how it works or do I need to explain?

[red yacht]

i think i know

but dont see the correlation

[kindred fulcrum]

So you find gcd(a,b) by using the fact that gcd(a,b)=gcd(a,b-a)

I don't really know to explain this generally

So with an example:
gcd(7,11)=gcd(7,4)=gcd(3,4)=gcd(3,1)=1

[red yacht]

7 and 11 are coprimes

so?

[kindred fulcrum]

Whats important is how we got to that

Let me continue

[red yacht]

I hear you

continue please

(?

[kindred fulcrum]

So you know
3 * 1 - 1 * 2 = 1
4 = 3 * 1 + 1
7 = 4 * 1 + 3
11 = 7 * 1 + 4

So you can work backwords using these equations to find an a,b that give 7a + 11b = 1

And then you can multiply by 10

[red yacht]

where is this coming from

seems out of the blue

[kindred fulcrum]

This comes out of division with reminder

[red yacht]

division of what

[kindred fulcrum]

4 by 3
7 by 4
11 by 7

[red yacht]

thats what I mean

we were talking about 7a + 11b = 10

gcd(7,11)=gcd(7,4)=gcd(3,4)=gcd(3,1)=1

[kindred fulcrum]

.

[red yacht]

WTF is going on

[kindred fulcrum]

So I found a solution for 7a + 11b = 1

And after multiplying by 10,
7 (10a) + 11 (10b) = 10

[red yacht]

what

there are multiple other solutions we are missing

[kindred fulcrum]

Yes, but these can be found easily once we have one solution

[red yacht]

we already know a solution to 7a + 11b = 10, its (3,1)

[kindred fulcrum]

But as you said earlier, this was by guessing

I went through an algorithm

[red yacht]

why did you not do 3/1

[red yacht]

3/1, 4/3, 7/4, 11/7

[charred roost]

Ages ago I made an animation to explain the extended Euclidean algorithm, maybe it helps? It's a bit crappy, but I think you can see how keeping track of coefficients helps you find the x and y such that ax + by = gcd(a, b)

[red yacht]

i guess

too much stuff moving around for my taste but I kind of got it after rewatching it multiple times

[red yacht]

i see, so this is why squeeze squeeze said that he wanted to solve 7a + 11b = 1 first

[charred roost]

yeah, if you can find a, b such that 7a + 11b = 1, then it's straightforward to find a, b such that 7a + 11b = 10

[red yacht]

how can you figure out the pair (3,1)

@kindred fulcrum @charred roost

7a + 11b = gcd(7,11)

7a + 11b = 1

gcd(7,11)=gcd(7,4)=gcd(3,4)=gcd(3,1)=1

[charred roost]

first you posted in #proofs-and-logic , then you posted here, now suddenly you're in a help channel getting help for the exact same problem

[red yacht]

i pinged and nobody replied

[charred roost]

well you can atleast tell us that you went somewhere else, so we're not wasting our time

[red yacht]

no time was wasted because nobody replied 🥀

[charred roost]

I was about to help, but I'm not being paid for helping you, so I can't always reply immediately

[red yacht]

is fine, I am already cooked for my exam

i think i will need to retake this crap

diophantine eqs are lowkey nightmare-ish

[charred roost]

you'll get used to it

[zealous thorn]

Last three digits of 25^63×63^25

I am sure mod 125×8

25^63 mod 125

25^63 mod 8?

[tall arch]

25^63 = 0 (mod 125)

25^63 = 1^63 = 1 (mod 8)

[kindred fulcrum]

Already solved in #help-47

[red yacht]

need help with ii)

maybe we need to use bezouts lemma

also, gcd(20,16) = gcd(4,16) = gcd(4,12)= gcd (4,8) = gcd(4,4) = gcd(4,0) = 4

from there we use bezouts identity

20a + 16b = gcd(20,16)
20a + 16b = 4
one pair is (a,b) = (1,-1)

also, 20(16) + 16(-20) = 0

but from here I get stuck

[kindred fulcrum]

You have the stronger 20 * 4 + 16 * (-5) = 0

[red yacht]

seems out of the blue to me

[kindred fulcrum]

And since 4 and -5 are coprime then all of the solutions are
(9 + 4k, -9-5k)

[kindred fulcrum]

Divided by gcd(16,20)

[red yacht]

steps where skipped

[red yacht]

i figured, yeah 4 and -5 work, though I dont see where the 9 is coming from(?)

[kindred fulcrum]

36 = 4 * 9

And you worked out a solution to be (1,-1)

[red yacht]

seems out of the blue

you divided both sides of the diophantine by 4

[kindred fulcrum]

You knew 20 * 1 + 16 * (-1) = 4
So multiplying by 9
20 * 9 + 16 * (-9) = 36

Same things from yesterday, transforming a pair from bezout to a solution of your original equation

[red yacht]

seems a little bit out of the blue to me and non systematic. Care to elaborate?

[kindred fulcrum]

You found a particular solution to 20x+16y=4

[red yacht]

but I want to find all the pairs for 20a + 16b = 36

[kindred fulcrum]

So you multiply by 9 and find a particular solution to your equation

[red yacht]

care to elaborate?

[versed flax]

so here you have a solution to the equation 20a+16b=4

but as you said you want all solutions to the equation 20a+16b=36

[versed flax]

a solution to this is (1,-1) as you said.

[versed flax]

but 36=4*9

so if you have a solution to the equation 20a+16b=4 then to get a solution to 20a+16b=36 you only need to multiply the solution of the first eq that you have by 9. Do you agree?

[red yacht]

i domt think i dollow

[versed flax]

ok where are you lost so that i can try to help

so you have 20(1)+16(-1)=4 right?

multiply both sides of this equation by 9

on the RHS you get 36

on the LHS you get 20(9)+16(-9)

so (9,-9) is a solution to the equation 20a+16b=4

does that clear things up?

@red yacht i will go eat rq and come back, in this time read what i wrote and if there is something you dont understand tell me what is it

[red yacht]

what are you about to eat?

[versed flax]

i am back

[versed flax]

i ate fried eggs

i also ate a bit of goiabada, idk if you know what that is

[versed flax]

so did you get what i wrote above?

[kindred fulcrum]

#book-recommendations

[rare dock]

Mybad

[kindred fulcrum]

just pointing you to where you can get answers

you did nothing wrong

[rare dock]

Oh , i thought i broke a rule or something

[marsh briar]

What kind of drugs are contest math people on?? For ref I'm mostly a real analysis type of person and tried doing one of my high school's caml problems, half the problems I don't know where to start and the other half were pretty simple, one of the simplish problems was this one.

Find the average of palindromes from 1000-9000

The way I approached this was probably somewhat bruteforced'ish. From some of my linear algebra background I thought of this more-so as a combination of 1001*n + 110k, whereas n can be values from 1 to 8, and k can be 0 to 9, so 8 and 10 choices respectively. Combining those choices (nk) I got the total number of choices, 80.

Noticing that I could break apart the sum into two ( due to the two independant variables ) I got k* sum 1001n + n*sum 110k

[rugged locust]

yeah, competition math is very different from university math

[marsh briar]

THEN THEY DID OH HEY [8998 + 1001]/2

[rugged locust]

a lot less of the skills you pick up from doing uni math transfer than you would expect

[marsh briar]

HOW DO YOU EVEN FIGURE THAT OUT???

[
\text{Total} =\left[k\sum_{x\in{n}}1001x+n\sum_{y\in{k}}110y\right]
]

[sterile pumice]

Makenna

[marsh briar]

Definitely, I'm not sure if it's my inexperience showing but I feel like contest math is more of cheap tricks than logic

( Speaking of the AMC/CAML/other lower level high school contest math )

if you're in the IMO or Putnum you have the highest level of mathematical maturity behind you

Had to add the last bit before I got cancelled

[carmine tide]

yeah as someone who did comp math in hs, there's a learning curve of tricks and out of school content

and then it just goes to wherever it wants to go

lol

[marsh briar]

From our probably much wider experience with these problems, would you say that without knowing the tricks could you solve the majority of problems with logic/general math alone?

I feel like there is no beauty in a problem that relies on a very random theorem

By random I mean like not well known in general math

[carmine tide]

https://artofproblemsolving.com/wiki/index.php/2021_Fall_AMC_10A

I did this test with no experience and no preparation in my first year of high school and got 15 right, 7 blank, and 3 wrong

so

ig take from that what you will

Let me see if I can piece together which ones I did

[marsh briar]

I feel like contest math this way pushes away people that like math, as many math clubs are mainly focused on contest maths rather than general proof based maths

[marsh briar]

First question is a bit odd, is this using a calculator? By odd it just is if you had a calculator it would be fairly trivial but if you didn't the solution seems hard to come to ( via the solution set process )

[carmine tide]

Found my score report: I did 1-11, 13, 16, 18, 20 correct; 14, 23, 25 wrong; the rest blank

[carmine tide]

no calculators

75 minutes

2112 - 2021 = 91

$\frac{91^2}{169}=\frac{91^2}{13^2}=7^2=49$

[sterile pumice]

Civil Service Pigeon

[marsh briar]

ew $ user ( jk )

I was joking we should memorize all years from the current to 20 years ago and their prime factorizations because those seem to come up way too much lol

[carmine tide]

You generally memorise the current year

people with experience generally have the previous few years memorised since they competed in those years as well

beyond that

eh

typically if it's some funky prime they'll tell you

[marsh briar]

Haha

AH

[carmine tide]

2014 amc 12b p23 is the first example that comes to mind

[marsh briar]

to be fair I think it's just my hate of memorization, and the feeling that contest math has a large majority of it makes me a bit uncomfortable

[carmine tide]

[https://artofproblemsolving.com/wiki/index.php/2014_AMC_12B_Problems]

[carmine tide]

yeah I memorised a fair bit less than other people (basically memorised just enough to derive anything else that I'd need fairly quickly)

didn't hurt me too badly

good contests don't make you memorise everything under the sun

hmmt

[marsh briar]

Yeah, I do the same with calculus really. Although it has not went so well in my current calculus class as time has been a prime factor in my test taking.

[marsh briar]

From doing real analysis I've been scarred all too much from the derivations of the derivative rules that I can normally calculate the trig functions from sin->cos alone

[carmine tide]

oh I do that too lol (all hail using s and c as shorthand for rushed derivations)

[marsh briar]

Although it is definitely not time efficient.

As someone with a bad memory it feels like a decent memory ( like being able to memorize the unit circle or derivative /integral trig functions without thinking ! ) is like cheating

[carmine tide]

eh a lot of what I have memorised is from ad nauseum usage so

[marsh briar]

Most of the problems we do are fairly trivial if you just have the memory, and it feels a bit cheap in that sense

[carmine tide]

rip

[marsh briar]

I'm a bit disappointed in the lack of any real proofs ( / derivations ) in my class

and it doesn't show how pretty math can be

[carmine tide]

wait you're in analysis and don't do real proofs?

tf

[marsh briar]

Well, I'm a high school that is in a calculus class that happened to do real analysis in my freshman/soph year

Just self study mainly, as my graduate physics friend urged me to learn it.

[carmine tide]

ah

tropo what do you have to say

[marsh briar]

We are getting a whole 50 page research paper introduction here

[wooden glen]

Not sure if you're looking for an answer, but: Whenever n is a palindrome between 1000 and 9000, then 9999-n is also a palindrome between 1000 and 9000. This is an involution and has no fixed point (since odd palindromes map to even ones and vice versa). So we can pair all the palindromes off like that, and each pair individually has an average of 9999/2.

[carmine tide]

(pairing is a pretty common thing in comp math)

[marsh briar]

sounds fairly specific

[wooden glen]

Yes, contest math very often requires problem-specific insights.

[marsh briar]

That's interesting!

I got the same answer anyways, but it seems like a more roundabout method that I used

[carmine tide]

^^ although pairing is a general technique in a variety of contexts

not just in comp math

Example: handshake lemma [https://proofwiki.org/wiki/Handshake_Lemma]

[wooden glen]

Yeah, but coming up with that specific pairing is rather problem specific still.

[carmine tide]

true

[tall arch]

i feel like the general strategy fo these problems is expected value

[marsh briar]

Oh, like what?

[junior swallow]

Can somebody help me see why we can make this assumption? If g^{p - 1} \equiv 1 (p^2), then I get 1 + ( p -1)g^{p - 2}p \equiv 1 - g^{-1} p (p^2), but I don't see what this means

[wooden glen]

The reasoning must be, "if the g you pick first happens to give you g^(p-1) == 1 (mod p^2), then replace it with g+p instead".

The "since p² does not divide" is a way to say that (p-1)g^(p-2)p is nonzero modulo p². So adding (p-1)g^(p-2)p to 1 produces something that isn't 1.

[red yacht]

can I get some help with iv)?

gcd(1555,300) = gcd(55,300) = gcd(55,25)

= gcd(30,25) = gcd(5,25) = gcd(5,0) = 5

we might need to use bezouts lemma

[wooden glen]

You don't even need to meticulously compute the greatest common divisor, since it is clear that 5 is a common divisor, and thus everything that can be made as 1555a-300b will be divisible by 5.

[red yacht]

well 5 does not divide 11

[wooden glen]

So there you go.

[red yacht]

whats your point? sorry I think it went over my head lmao

you here? @wooden glen

[wooden glen]

My point is that since 1555a-300b is always divisible by 5 and 11 isn't, 1555a-300b is never equal to 11.

I don't understand the Spanish text, but I'm betting on "there are no such pairs" being a possible answer to the question.

[red yacht]

yeah thank you for the help

idk what I was thinking

[red yacht]

can I get some help with 2)

find all the pairs in Z^2 which satisfy
4|a, 8|b, 33a + 9b = 120

[weary fog]

i feel like the general strategy fo these problems is expected value

[tall arch]

Let a=4x b=8y for integers x and y and then simplify

[tall arch]

Wut

[red yacht]

care to elaborate

[red yacht]

ragebaiting I think (?) else. elaborate

[red yacht]

i think this is cooking something, i just dunno how to connect the pieces

[patent acorn]

4 | a means that a = 4x for some integer x, and similarly 8 | b means that b = 8y for some integer y
so you can just substitute these values in and say we're trying to find pairs (x,y) that satisfy 33(4x) + 9(8y) = 120

and then of course at the end, once we've figured that out, we'll have to translate back into the (a, b) pairs like the question is actually asking for, but that shouldn't be too hard

[junior swallow]

Oh thanks, I see! So basically, if g^(p - 1) = 1, then we can just replace it with g + p because they're equal, and we have g + p \neq 1 mod p^2 since (p-1)g^(p-2)p is nonzero modulo p^2 like you said

Wait but aren't g and g + p only equal mod p?

If so why can we replace g with g + p then?

[wooden glen]

The requirement at that point is that g is a primitive root modulo p, and that g^(p-1) differs from 1 modulo p².
Adding p preserves the first part, and makes the second part true if it wasn't already.

[junior swallow]

Oh ok thank you so much

That makes things much more clear

[red yacht]

where did the 120 came from? srry i misread

[red yacht]

then what? can I divide everything by 4?

33x + 9(2y) = 30

gcd(33,18) = gcd(15,18) = gcd(15,3) = gcd(0,3) = 3

@patent acorn

am I missing something here?

[red yacht]

care to elaborate?

so the original equation is
33a + 9b = 120

4 | a <=> ∃x ∈ Z, s.t. a = 4x
8 | b <=> ∃y ∈ Z, s.t. b = 8y

33(4x) + 9(8y) = 120

then we can divide both sides by 4?

33x + 18y = 30

gcd(33,18) = gcd(15,18) = gcd(15,3) = gcd(0,3) = 3

11x + 6y = 10

22 - 12 = 10

so

(x,y) = (2,-2) is a solution to 11x + 6y = 10

so

11(-6) + 6(11) = 0

so

11(2-6k) + 6(-2+11k) = 10

with k ∈ Z

now what ? @patent acorn

the thing is we need to go back to a = 4x and b = 8y

so we need to multiply by 4?

11(8-24k) + 6(-8+44k) = 40

[red yacht]

something like this?

[red yacht]

sorry for the late response I was having breakfast

you here?

[versed flax]

You are almost there

The only error you have is in -8+44k

Remember that b=8y and not 4y

So you have to multiply y=-2+11k by 8

your a is correct since a=4x

@red yacht

[red yacht]

what happened?

[red yacht]

yeah i think I am close, help me finish dawg

[patent acorn]

y = -2 + 11k

b = 8y

so you should have done 8(-2 + 11k) = -16 + 88k

[red yacht]

wtf?

can we start from the beginning

[left fable]

wheres your beginning renato

[red yacht]

like did you see the exercise I sent

[red yacht]

care to elaborate?

i got lost at that step

[versed flax]

You found x and y

Now you want to find a and b

a=4x and b=8y

Now substitute the values of x and y that you got in these 2 equations and you are done

[red yacht]

when?

[versed flax]

Here

[red yacht]

nice

now what?

11(8-24k) + 6(-8+44k) = 40

now what?

you here?

11(2-6k) + 6(-2+11k) = 10

this?

or this

11(8-24k) + 6(-8+44k) = 40

???????

[versed flax]

Here

You got that x=2-6k and y=-2+11k

[red yacht]

yes

[versed flax]

Now a=4x and b=8y

[red yacht]

but we want 4x and 8y

[versed flax]

So a=??? and b=???

[red yacht]

a = 8-24k

b = -16+88k

i appreciate the help lads, I am getting better at basic diophantines

❤️ I appreciate everyone who helps me

thank you guys, this problems are kinda fun, ngl (?)

[weary fog]

That's interesting!

[unique cypress]

Galois representation when

[tall arch]

Group presentation about group presentations when

[red yacht]

this is for my Algebra I class, I will see galois theory if and only if I manage to get to Algebra III, but this is off-topic

[abstract ferry]

I mean Galois theory is used a lot in number theory thingy so that is really not real issue (that it is offtopic)

like some topics in elementary NT are literally parts of fields and Galois theory

[rugged locust]

Have you started algebra yet?