elementary-number-theory

[drifting imp]

If I have a composite function g(f(x)) why is the domain not the co domain of f(x) since that is the input of g(x)

[wooden glen]

The domain is the set of things you can use as input to the entire composition.

[drifting imp]

Right so the set would just be the co domain no?

[wooden glen]

The codomain of f is neither the domain nor the codomain of g o f.

[drifting imp]

Y not

When the output of f is the input of g in g f

[wooden glen]

Therefore those things are neither the input to g o f nor the output from it.

[drifting imp]

Wait

So the domain of gf is just the domain of f

[wooden glen]

Yes.

[drifting imp]

And the codomain would be the codomain of g?

[wooden glen]

Yes.

[drifting imp]

I see

I was thinking of the two functions separately

But f has to be valid before it can be put into g so the domain must be from f

[wooden glen]

Suppose $f:\bN\to\bR$ and $g:\bR\to\bC$. You can't use an arbitrary real number as input to $g\circ f$, so $\bR$ cannot be the domain. Neither can you be sure that the output fo $g\circ f$ will always be real, so $\bR$ cannot be the codomain either.

[sterile pumice]

Troposphere

[verbal cedar]

for a given $a\in\bZ$ and $n\in\bN$, is there a name for or way to indicate the integer $\alpha$ satisfying
$$\alpha\equiv a\pmod{n},\quad 0\leq\alpha<n$$

[sterile pumice]

nilpotent nix

[verbal cedar]

i have an expression which gives a difference of integers (z2-z1), but what i really need is the least nonnegative congruent integer of that difference. is there a compact way to notate that? like [z2-z1] or something idk

[dusty dragon]

You can use the equivalence notation $[a]$ to indicate $[a] = { a + nk : k \in \mathbb Z }$. So you can say that $\alpha \in [a]$ to mean that $\alpha \equiv a \pmod n$

[still flare]

That's called the remainder.

[wooden glen]

It's sometimes written as $a \bmod n$, though some feel that is to computer-sciencey to be used in serious math.

[sterile pumice]

Troposphere

[sleek spire]

I am not sure whether this is the right channel for this, but how do I show that there exists no $x \in \bQ$ such that $\sqrt[3]{2}^2 x \in \bQ$?

[sterile pumice]

rectangle cube

[still flare]

You are asking whether or not the cubed root of 2 is rational. Have a look at the proof that the square root of 2 is irrational, and try and generalise it to arbitrary roots of 2.

[wooden glen]

But there is: x=0 satisfies that.

[sleek spire]

x \in \bQ \setminus \Set{0}

:p

[sleek spire]

oke thanks!

[tacit heart]

Which theorem goes along these lines? : $(1 + n)^{p^r} \equiv 1 + n^{p^r} \pmod{p}$

[still flare]

This is known as the freshman's dream

[tacit heart]

what

[still flare]

I'm not joking

[tacit heart]

oh

[still flare]

it's a bit of a mean name

See: https://en.wikipedia.org/wiki/Freshman's_dream#Prime_characteristic

[sterile pumice]

kappa

[tacit heart]

Aren't these different?

[still flare]

No

[tacit heart]

"A related theorem states that if p is prime then (x + 1)p ≡ xp + 1 in the polynomial ring {\displaystyle \mathbb {Z} _{p}[x]}{\displaystyle \mathbb {Z} _{p}[x]}."

[still flare]

If you're referring to how one doesn't have a power of r, that comes from repeated powers of p. It follows from induction.

[tacit heart]

Yea but what's the related theorem's specific name?

[still flare]

It is called the freshman's dream

that is the name

they talk about the proof there

[wooden glen]

I don't think the corollary where the exponent is p^r rather than p has a name of its own.

[tacit heart]

Ok thanks!

[torn escarp]

I'd suggest asking #competition-math instead

[polar ruin]

Isn’t this number theory though?

Well if u say so

[fluid steppe]

pretty big overlap between the 2 ngl

[torn escarp]

I wouldn't say this is nt, this isn't really about integers or rational numbers it's more about an inequality of real numbers

[polar ruin]

Ah mb

[torn escarp]

it's not too serious, there is a lot of overlap, it's just I thought you might get better results asking there

[polar ruin]

I see thanks

[white lion]

hey anyone know whats wrong here? it's related to pythagorean triples

so we have here (s,t) = (3,4) => (x,y,z) = (2st, t^2 - s^2, t^2+s^2) = (24,7,25)

there is a result that states that 3|y for all y

but here in this case y=7 and 7 isn't a multiple of a 3 obviously

what am I missing here?

but 24^2+7^2=25^2 is a true statement

[torn escarp]

I guess since 3 | 24 you have flipped x and y

I'm not familiar with the result you describe but from this form it's not hard to show at least one of x or y must be divisible by 3. If s and t are not divisible by 3, then y=t^2-s^2 is divisible by 3. If one of s or t is divisible by 3, then x=2st is divisible by 3.

this means only exactly one of x or y is always divisible by 3, but you could always rearrange them so that y was the one that's divisible by 3 if you wanted

[white lion]

@torn escarp but y is always equal to t^2-s^2 (and t>s always because y>0) and that would be 7

[torn escarp]

this says 3 | x in the first line

[white lion]

oh right

ok I got it thanks so much <4

[torn escarp]

yeah you're welcome 👍

[white lion]

what about in the case of (3,4,5)

we know that x=2st

2st=3 doesn't make sense though that would mean s or t isn't an integer

[torn escarp]

yeah, the formula generates primitive pythagorean triples, but that doesn't mean you can go backwards by picking them and working out what s and t are

3=s^2-t^2, 4=2st, 5=s^2+t^2 with s=2 and t=1 is what would generate this one

[torn escarp]

Fix an integer $n$, are there integers $a,b$ with $1\le a \le n-1$ such that $a^2-b^2(1+n^2)=\pm 1$? My guess is no, and I verified this up to n=10,000 by computer (unless I made an error in my code). If that guess is correct, it should prove $n-\sqrt{1+n^2}$ is always a fundamental unit in $\bZ[\sqrt{1+n^2}]^\times$.

[sterile pumice]

mOwOsity

[torn escarp]

actually I think there's a trick for showing a solution is minimal for pell's equation

[fervent grove]

[any] unit a + b*sqrt(n^2-1) with minimal [nonzero] |b| should be [fundamental], right?

I'm pretty sure taking powers uniformly increases the height of the coefficients here

or something

[torn escarp]

oh yeah good point, since I'm already at |-1|=1 it should be minimal, N(n-sqrt(n^2+1)) = -1 should be a unit then

powers will only raise it, that was conveniently easy haha

thanks

[verbal cedar]

given that $n\geq3$ is an odd integer, and
$$k\equiv 1\pmod{n},\quad k\equiv d_0\pmod{2}$$
is there a way to solve for $k$?

[sterile pumice]

nilpotent nix

[verbal cedar]

ik a solution exists by the Chinese remainder theorem, but not how to find it

[stiff rivet]

why not just check for d_0 = 0, 1

[dusty dragon]

Let $k = 1 + nt$. Then $1 + nt \equiv d_0 \pmod 2$ or equivalently $nt \equiv d_0 + 1 \pmod 2$. But this implies that $t \equiv n^{-1} (d_0 + 1) \pmod 2$. You now have an expression for $t$ so you have an expression for $k$

[dusty dragon]

In particular, you can write $t = n^{-1}(d_0 + 1) + 2m$, which implies that $k = 1 + (d_0 + 1) + 2mn$. In other words, $k \equiv d_0 + 2 \pmod{2n}$

[torn escarp]

Well, if k is a positive integer, the smallest k could be is 1 just by looking at k=1 mod n. Now if d_0=1 mod 2, then it agrees there too. If d_0=0 however, then because n is odd, we can say k=1+n.

we could package this up nicely as k=1+n(1-d_0)

since that's the minimal positive k, you could just add any arbitrary multiple of 2n to it

[torn escarp]

oh as far as this is concerned, you can use the CRT to find the answer explicitly, let me give an example. Let's say you know n=a mod p, n=b mod q, and n=c mod r for distinct primes p, q, r.

Now we know by fermat's little theorem that $(qr)^{p-1}$ will be 1 mod p but it's also 0 mod q and 0 mod r. This trick lets us combine all the solutions without them interfering with each other

[sterile pumice]

mOwOsity

[torn escarp]

So hopefully it's clear, $$n=a(qr)^{p-1} + b(pr)^{q-1}+c(pq)^{r-1} \mod pqr$$
If you reduce this, say, mod r, you can see it'll recover where you came from
$$n=a0 + b0+c*1 \mod r$$

[sterile pumice]

mOwOsity

[torn escarp]

admittedly this might not be the best route to take, but at least I wish someone had shown me this when I first learned it

[pine badge]

For a positive integer m how could I find all values c such that
c = m - (n*a)
Where:
n is a positive integer < m
a is a positive integer <= floor((2m+1)/2)
And c is any integer + or -, from (n+1)^2 mod 3 to n(n-1)/2, that is even if n mod 4 is in {0,1} and odd if in {2,3}.

My way has been to make a matrix with columns a, rows n, and entries c. Then just check if values of c meet the criteria for c.

[covert finch]

sorry I misworded this question

is this statement true?
if a^n = 1 (mod b) for some n, then a and b must be relatively prime

basically, euler's theorem's converse

and if so how would you prove it

[sacred junco]

you can use bezouts lemma with a direct proof i think

bezouts lemma states that gcd(a, b) = as + bp for a certain s, p in integers

with mod proofs, try putting it into equation form

[covert finch]

alr so I have
a^n = bt + 1 for some t
a^n - bt = 1
a(a^(n-1)) + (-t)b = 1

it would be convenient if I could show that a^(n-1) and -t are s and p, somehow

but s and t can only be some integers, not all

[dusty dragon]

It might be helpful to note that a^n = a * a^{n - 1}, which implies that a is a multiplicative unit in Z_b. But this is true iff gcd(a, b) = 1

[sacred junco]

but you showed the existence of such integers that form a linear combination to yield the gcd

which is enough for bezout i believe

[covert finch]

what does multiplicative unit mean?

I don't really see how a^{n-1} is relatively prime to b

[dusty dragon]

A multiplicative unit is an element that basically has a multiplicative inverse. In other words, we say that a is a unit of Z_n if there exist some b in Z_n such that ab = 1 (mod n)

[covert finch]

oh alr

but how does that lead to

But this is true iff gcd(a, b) = 1

[dusty dragon]

We prove that a is a unit of Z_b iff gcd(a, b) = 1.
(=>) Suppose that a is a unit of Z_b. Then, for some c in Z_b, ac = 1 (mod b). But this implies that there exist some y such that ac - by = 1. But, if a and b have a common divisor, then it must consequently divide 1. You can see this because any common divisor of a and b can be factored and since we are working over the integers, the common divisor must divide 1. But this only happens when the common divisor is exactly 1 (or -1). Therefore, gcd(a, b) = 1.

(<=) Suppose that gcd(a, b) = 1. Then, by Bezout’s lemma, there exist integers x, y such that ax + by = 1. But this implies that ax = 1 - by, which is equivalent to ax = 1 (mod b). Hence, a is a unit of Z_b

[sacred junco]

You just showed via bezouts lemma

You showed that a(a^(n - 1) + (-t)b = 1, which means you found two integers a, -t that make a linear combination of a^(n - 1) and b. Bezouts essentially shows that the gcd must divide all linear combinations. since the gcd divides 1 it must be 1 . You can prove bezouts using the well ordering property to all positive linear combinations of a and b for (gcd(a,b) = as + pb).

Now you can say because $a = p_1^{q_1} * p_2^{q_2} * ..., b = m_1^{n_1} * ...$ for their prime factorizations, you can find $a^{n-1} = p_1^{(n-1)q_1} * p_2^{(n-1)q_2} * ...$ Because $a^{n-1}, b$ are prime, they must have different prime factors, so it leads to $gcd(a, b) = 1$. Then you can show $a^n, b$ are relatively prime.

[sterile pumice]

JOKER

[covert finch]

Bezouts essentially shows that the gcd must divide all linear combinations
this was the key part I was missing, thanks

[covert finch]

this also helped, thanks

[sacred junco]

http://ramanujan.math.trinity.edu/rdaileda/teach/s20/m3326/lectures/bezout_handout.pdf this should resolve any doubts about this

[covert finch]

right that makes sense, since if you let gcd(a,b) = d, then d divides a and b, so for all ma + nb, you can write a and b as rd and sd for some r and s, so ma + nb = mrd + nsd = d(mr + ns) which is clearly divisible by d

[sacred junco]

yep

[torn escarp]

I don't quite understand the last part "And c is any integer + or -, from (n+1)^2 mod 3 to n(n-1)/2" are you taking (n+1)^2 mod 3 then reducing to something in {0, 1, 2}? But that kind of means c will always be positive, but you said it could be negative, so doesn't seem quite right to me

also floor((2m+1)/2) = floor(m + 1/2) = m since m is an integer, so you can simplify that part slightly

[green linden]

hi guys. is this solution to this question correct?

PS: Please tag me incase anyone answers

[torn escarp]

not quite, two gaussian integers are associate if they differ by a unit. It looks like you found the units, but there are more elements that are nonunits that differ by a unit. Maybe look at u*(a+bi)=a-bi and pick u from {1,-1,i,-i} and see what constraints this places on a, b to make it true.

hint: ||there are infinitely many||

[fervent crest]

Oh this is so much easier than what I did, which was by writing out (a+bi)/(a-bi) and seeing when is this even a gaussian integer

[torn escarp]

actually I find it easier to think about geometrically cause complex conjugation is reflection and units give 90 degree rotations, this makes it kind of obvious to me that the only lines fixed are along the + and X

[fervent crest]

Yeah

[pine badge]

Sorry my definition made no sense,
Maybe better way to say is
r = (n(n-1))/2
c is any odd integer from -r to r if r is odd and any even integer from -r to r if r is even.

[pine badge]

The floor bit is not too important as I beleive using values of a outside this range will never land in the desired c range.

[pine badge]

So can be:
For a positive integer m how could I find all values c such that
c = m - (n*a)
Where:
n is a positive integer < m
a is a positive integer < m
And c is any odd integer from -r to r if r is odd and any even integer from -r to r if r is even.
Where r = (n(n-1))/2

This does ignore the obvious c=0 when a=m and n=1.

[torn escarp]

nothing jumps out at me, maybe working out some stuff by computer would make a pattern more obvious idk

what's this for btw

[pine badge]

Ok, thanks for thinking about it, this is for trying to find some expression for the number of compositions of m where the differences of adjacent parts is in {-1,1}.

[torn escarp]

oh you want to count the number of c values, not necessarily describe them with a formula?

or wait, what's a composition, some kind of ordered partition, like 6=1+2+3 would be an example but 6=1+3+2 doesn't since 1 and 3 are more than 1 apart kind of thing?

[pine badge]

Yea

[torn escarp]

at least, I'm wondering about making a generating function for it unless you already have one

or maybe simpler, a recurrence relation

[pine badge]

No I don't have a generating function, for the number of compositions

But for the c values, I want to know which values of c work with which n and a. So more than just count

[torn escarp]

I guess some crude upper bound is the number of ordered partitions is we can imagine n stones with n-1 dividers between them, that gives us 2^{n-1} ordered partitions. We can then look at divisors of n, since for instance 4=2+2=1+1+1+1 correspond to the 3 divisors of 4, tau(4), although the single number n itself is fine, so 2^{n-1} - tau(n)+1 >= c_n I guess

idk probably there are better bounds lol

but you want to have them explicitly I see

[pine badge]

Oh that's a nice way to remove compositions with the same parts

[torn escarp]

there's also gonna be a symmetry with like, 2+1 and 1+2 but you have self-symmetric cases like 1+2+1

trying to work out a recurrence relation by thinking about how to make them, I think something like looking at breaking it into k parts and considering that first, then adding all those easier cases up maybe

[pine badge]

Also think the a needs to be bounded lower than <m.
Yes, this is why I look at the c values for n and a. n is the number of parts minus one and a is the first part of the composition

[torn escarp]

at least, that corresponds to how to get the numbers explicitly too

[pine badge]

I think it works by checking a matrix of all c values with columns aand rows n in the desired ranges.
Then r gives a desired range of c for each row.
If a row has a value c in that range, that corresponds to one or more valid composition.
Then to find out how many valid compositions for that c value, there is another process geekotechy, came up with in the combinatoric structures page

But this process is long and confusing lol

[torn escarp]

I would just brute force them with a python program lol

[pine badge]

Brute force I thought this was a math server

[torn escarp]

haha

[pine badge]

There is an oeis entry. Others have brute forced to large m

[torn escarp]

I think I have a fairly simple way that might be similar to yours, for finding them. Basically for breaking it into k parts, you have some equation like n=x+(x+1)+(x+2)+(x+1)+(x+2)+(x+3)+... where you stop at k terms and each constant in each term is incremented or decremented by 1, so really it becomes n=kx + a, where a is this aggregate number independent of n and x, only dependent on k

because there are k-1 choices to make for +1 or -1, this means there are 2^{k-1} different "paths" to take, which is kind of large I guess, although it's symmetrical so we can halve it to 2^{k-2}

main thing is having these aggregate numbers 'a' lets us check if n-a = 0 mod k

if yes, then it's a composition

so I'm thinking brute force these 2^{k-2} different a values with n... for each k<inverse function of (n(n+1)/2)

probably there are better ways, but that's best I got for now lol

the fact that these a numbers are independent kind of seems neat to me, but maybe this is a red herring

[pine badge]

But once you get to a 1 there is only one choice

[torn escarp]

oh I might be over counting by letting in negative values or 0 or something hmm

link me the oeis

[pine badge]

Ok let me find the number

[torn escarp]

I imagine we're not gonna be able to do much better than they have done, so if they say stuff like "equivalent to the euler-ramanujan numbers divided by the erdos-bernoulli numbers squared"

[pine badge]

A173258

Strange cause for early values the number of compositions even goes down

[torn escarp]

yeah, I guess it's too tightly packed or something

addition and multiplication are both sorta creeping into compositions, seems really difficult

they're pretty rigid too, like at first I was thinking we could make a recurrence relation by trying to make compositions from the smaller compositions, but that's not really so easy cause each composition depends on what numbers are on the left and right ends

[pine badge]

So each number m can be composed into 1s and 2s, this is the longest length form. Then each odd has a one of length two, even has a length three.

[torn escarp]

yeah, this is sorta how I was looking at the "aggregate numbers" earlier relating to the modular arithmetic aspect

although I was being a bit too reckless and that would allow non positive numbers

like 1s and 2s corresponds to m=x + (x+1) + x + (x+1) + ... sort of case

I guess our perspectives on the same case are slightly different though hmm

[pine badge]

How so?

[torn escarp]

I was looking modulo the number of terms appearing, you're looking modulo m, the number itself

[pine badge]

Oh ok

The c value thing was modulo a, the first part I thought?

[torn escarp]

I think my a value is different than yours I think

I should have used a different letter lol

gonna think more about this

[pine badge]

Hmm, as m gets large the way you were thinking about the space of possible compositions being symmetric is valid. For small m the compositions are mostly in the non symmetric space involving 1s and 2s.
Maybe the compositions could be split into one's coming from The symmetric tree space of choices . And some other kind.

[torn escarp]

I was able to come up with a recurrence relation if I split it apart a bunch

define $C_n$ to be the number of compositions of n, then define $C_{n,k}$ to be the number of compositions of n that have their last number k. Then it's clear that $C_n=\sum_{k\ge 1} C_{n,k}$. Now -

[sterile pumice]

mOwOsity

[torn escarp]

we can make $C_n$ alternateively from the smaller parts by looking at $C_{n-k,k\pm 1}$, since taking a composition of $n-k$ that ends in $k-1$ or $k+1$ will let us add $k$ to it to make $n-k+k=n$, so: $$C_n=\sum_{k \ge 1} C_{n-k,k-1}+C_{n-k,k+1}$$ with the convention that $C_{n,0}:=0$ for the edge case, since 0 is never the last number.

[sterile pumice]

mOwOsity

[torn escarp]

well maybe recurrence relation is the wrong thing, but a bit more playing around probably can turn this into a recurrence relation or generating function

the key fact is $C_n$ is being made out of $C_{m,k}$ with $m<n$

[sterile pumice]

mOwOsity

[torn escarp]

or actually I could refine it into a recurrence relation by writing it as $$C_{n,k} = C_{n-k,k-1}+C_{n-k,k+1}$$ since I'm making a term that ends in k, ok cool

[sterile pumice]

mOwOsity

[torn escarp]

after I eat I think this could be turned into a generating function with two variables and maybe something can be thrown at it like snake oil

[pine badge]

Oh wow, I will also look at this more after lunch

[pine badge]

I see how this builds them up from previous ones, recursively

Nice

[junior swallow]

im a bit confused about this corollary from pascal's identity

it states that for any fixed integer n greater than or equal to 1 and n greater than or equal to k, 2 * (n choose k) is equal to (n + 1 choose k).

however pascal's identity states that (n choose k) + (n choose k -1) = (n +1 choose k)

but from 2 * (n choose k), wouldn't we have 2 * (n choose k) = (n choose k) + (n choose k) which is not equal to (n choose k) + (n choose k - 1)

[fervent crest]

I don't think that's true, can you send a full screenshot of what the statement is?

@junior swallow

[junior swallow]

oh LMFAO I posted it to chat gpt 😭😭😭

And it said it was true

Ayo @cunning plinth what’s good lmao

[cunning plinth]

hi

[fervent crest]

Chat gpt is not good at doing math

[junior swallow]

Yea now that I look at the proof it gave it’s not completely true….

[fervent crest]

Yeah cause like you pointed out

$\binom{n+1}{k}=\binom{n}{k}+\binom{n}{k-1}$ so if $2\binom{n}{k}=\binom{n+1}{k}$ then $\binom{n}{k}=\binom{n}{k-1}$ which is not just true

[sterile pumice]

Whoever

[fervent crest]

It's saying consecutive numbers on the pascal triangle are the same

[junior swallow]

Right that makes sense

Thanks bro

[dense scroll]

for b, I understand that I have to see if gcd(n,7) = 1, but I'm lost as to how I should do that

[still flare]

Hint: gcd(n, 7) = 1 if and only if gcd(n + 7k, 7) = 1, where k is any whole number

[torn escarp]

idk if I'm saying the same thing or not, but since gcd(3,7)=1 you can apply fermat's little theorem, so determine what the exponent is mod 6. hint: ||there are easy divisibility by 2 and 3 tests you can do to determine it||

[native monolith]

Can't see it for p-1 doesnt divide k

[fervent grove]

there are a couple ways to do this

I really like this question, so I'll give you a few paths:

• use the fact that every prime has a primitive root
• use Newton's sums on the equation x^{p-1}-1. namely, what are the roots of this polynomial?
• let a be an element whose order does not divide k. multiply the entire sum by a^k.

[native monolith]

Okay thank you

[uncut pumice]

Why is this true?
$$∑_{d=1}^∞\frac{μ(d)}{d²} = \frac{1}{ζ(2)}$$
where $μ$ is the Möbius function, $ζ$ is the zeta function

[sterile pumice]

Mattuwu

[torn escarp]

More generally this follows from the Euler factorization for zeta(s) at any s, not just s=2

$$\frac{1}{\zeta(s)} = \prod_p \left( 1 + \frac{-1}{p^s}\right)$$

[sterile pumice]

mOwOsity

[torn escarp]

if you imagine expanding this out, the coefficients on 1/n^s can only come from when n is square free, since only p occurs, and when they do occur, there's a -1 so the number of primes in the number is what gives the same thing in the mobius function

If you're not very familiar with dirichlet series, I'll give an example, if we look at the n=6 term, it will come exactly from (-1/2^s)*(-1/3^s) = 1/6^s

if you look at the n=4 term, since -1/2^s only appears once, there is no other term with 2^s in the denominator to multiply with it, it means 0/4^s is what we have

if you're not sure where the euler factorization comes from, I think there's a decent derivation on wikipedia, it's basically factoring the zeta function like the sieve of eratosthenes

[uncut pumice]

@torn escarp Thanks!

I get how the factorisation is equivalent to the dirichlet series of 𝜇 now

[torn escarp]

cool

yeah, it's pretty important that this works out, by analogy with regular power series the zeta function and dirichlet series of the mobius function play the same role as partial sums and finite differences with them cancelling out as telescoping series, which is really all mobius inversion is doing

[tacit heart]

$\text{If} \ k^a \equiv k^b \pmod{n}, \text{then} \ a \equiv b \pmod{\varphi(n)}.$

[sterile pumice]

kappa

[tacit heart]

Why is this true?

[fervent grove]

I think this is false

take n=7 and k=1 and a=0 and b=1

[verbal cedar]

suppose $n$ is even, but the following equation does have a solution
$$2k\equiv c\pmod{n}$$
is there a way to get a formula or expression for $k$?

[sterile pumice]

nilpotent nix

[verbal cedar]

<@&286206848099549185>

[wraith hull]

A closed expression?

[verbal cedar]

yeah

[wraith hull]

K is a natural?

[verbal cedar]

is it possible for a specific even n? preferably, I'd like a solution for arbitrary even n, but idk what's possible.

[verbal cedar]

k is an unknown integer

[wraith hull]

Aight

[loud moon]

@verbal cedar if c is odd then there is no solution, because the lhs and rhs have different parities. depending on the factorization of n there is potentially more than one solution for k (modulo n), but a generic one is, uninterestingly, k = c / 2 (mod n). what specific solution are you after?

in general if 2k = c (mod n) and n = 2m, i.e. is even, and c is even by necessity, then k = c/2 (mod n/2), the proof is easy: if 2k = c (mod n), then 2k = un + c for some integer u, so dividing through by 2, k = u(n/2) + (c/2), so k = c/2 (mod n/2). that should give you a full set of solutions for k, that is, k = c/2 + u(n/2) for all integers u

[verbal cedar]

yes, thank you. it's observations like this that I'm looking for.

the full system I'm working with is
\begin{gather*}
k_1\equiv d\pmod{2}\
2k_2\equiv m_1-d\pmod{n}\
k_1+4k_3\equiv d+m_0-m_1\pmod{n}\
2k_4\equiv c\pmod{n}
\end{gather*}

[sterile pumice]

nilpotent nix

[verbal cedar]

i can get explicit solutions for the k's when n is odd no problem. but I'm wondering if it's also possible when n is even (and assuming a solution does exist)

[verbal cedar]

(c,d,m0,m1 are all given constants)

[loud moon]

@verbal cedar we can see that m0 and m1 must have the same parity, since if you take the third equation mod 2 (which is valid since n is even) then we get k1 = d + m0 - m1 (mod 2), and since k1 = d (mod 2) we get m0 = m1 (mod 2).

that means that you can freely set k3 = 0, and just let k1 = d + m0 - m1 (mod n) and you are done. you can see this is not in contradiction with the first congruence

basically the system is underdetermined

but if you want a non-zero k3, then it's straightforward to observe that you can just pick any k3 and adjust k1 accordingly to satisfy congruence (3), it won't affect the parity of k1 and therefore won't break congruence (1) and you are good to go

[uncut pumice]

Let 𝑝ᵢ be the 𝑖-th prime number with 𝑝₁ = 2, 𝑝₂=3 ..., How do you show that ∀ 𝑛, 𝑝ₙ ≥ 𝑛 + 1 ?

[still flare]

Note that p_i is odd for all i>1, so p_i >= 2i-1 > i for all i>1.

[uncut pumice]

oh no, so elegant, thanks!

just realized that's kinda a dumb question. with 𝑝₁ = 2, because primes only take integer values and is increasing, the rest of the primes have to be at least 1 or more larger than the subscript.

[sacred junco]

x = 10 (mod 12) and x = 4 (mod 5) so 10 + 12a = 4 + 5b. If we look at this equation mod 4, then we get b = 2 (mod 4), but this gives x = 14 + 20k for some integer k

That is not the solution, why?

[uncut pumice]

More generally, let 𝑎: ℕ → ℕ be an strictly increasing sequence, if 𝑎(𝑚) = 𝑛 for some 𝑚, 𝑛, then ∀ 𝑙>𝑚, 𝑎(𝑙) ≥ 𝑙+(𝑛-𝑚)

[torn escarp]

fun, trying to think of how to do better like Boytjie's, p_{3+2n} >= 5+6n and p_{4+2n} >= 7 + 6n since we know primes must be 1 or 5 mod 6 after 2, 3

I guess this could just be done arbitrarily further out by sieving further but it gets grosser

[sacred junco]

Can anyone please explain I'm really blanking on it

[torn escarp]

your final answer should be something up to a multiple of 60 since 12*5=60, you sorta picked mod 4 arbitrarily which is part of being a necessary condition

[sacred junco]

The real answer is x = 34 (mod 60)

[sacred junco]

I didn't pick it arbitrarily, I picked it because it makes the coefficient of b 1, and it gets rid of a

[torn escarp]

yeah, and 34=14 mod 20, you just stopped short

yeah, but in doing so you've not really solved the full problem, you haven't solved for them all the way

[sacred junco]

Why not?

I understand that I didn't but I don't know why

[torn escarp]

oh I think I see the nature of your misunderstanding

we're trying to combine something mod 12 with something mod 5, so you should be reducing your equation mod 12 or mod 5

I'd recommend mod 5

[sacred junco]

But why can't I use 4? 4 gets rid of the 12 too

[torn escarp]

4 divides 12, but it leaves an extra "3" unaccounted for

you could then go through and reduce mod 3 by what you plug in and that will finish it too

like say b=2+4c and plug that in 10+12a = 4+5(2+4c) now reduce mod 3 and solve for c

this is not the most efficient way, but hopefully seeing it this way helps show how to fill in the gap

[uncut pumice]

Fun, I just realized this is just an analogous of the mean value theorem, and the fact that the "derivative" of an increasing sequence of integers is lower bounded by 1

[sacred junco]

Okay wait let me try it

@torn escarp Something is still wrong

[torn escarp]

what do you get

[sacred junco]

So suppose we do that. Then we get 10 + 12m = 2 + 4n, looking at it mo 3, we get n = 2 + 3g

[torn escarp]

I'll show what I get, maybe this will help

I ended up getting c=1 mod 3

so I plug in:
x = 4+5(2+4c) = 4+5(2+4(1+3d)) = 34 + 60d

[sacred junco]

No you should get c = 2 mod 3?

[torn escarp]

show your work

[sacred junco]

10 + 12a = 2 + 4c so 1 + 0 = 2 + c (mod 3) => -1 = c (mod 3) => 2 = c (mod 3)

[torn escarp]

ah, no, you've plugged in b wrong, you need the rest of the equation there

x = 10+12a = 4+5b
x = 10+12a = 4+5(2+4c)

[sacred junco]

Oh okay I see, got it

[torn escarp]

cool

[sacred junco]

Thanks

[torn escarp]

You're welcome

in general though it's faster to do reduction mod 5 directly here

or you could do mod 12 directly too rather than breaking it up into mod 4 and mod 3

[uncut pumice]

Note that p_n >= p_{n-1} + 1, repeated use this:
p_n >= p_{n-1} + 1 >= p_{n-2} + 1 + 1 >= p_{n-3} + 1 + 1 + 1 ... = p_k + n - k
In particular, we have: p_n >= p_1 + n - 1 = n + 1

[torn escarp]

yeah I understand that argument, I was trying to do a better linear lower bound

[uncut pumice]

👍

[torn escarp]

for p>3 all primes are 1 or 5 mod 6, so if they were close together as possible it would mean 5, 7, 5+6, 7+6, 5+12, 7+12, etc are all prime

it's basically taking Boytjie's idea of primes p>2 are 1 mod 2, so 3, 3+2, 3+4, 3+6, etc would be the closest possible spacing

[uncut pumice]

But I guess linear bounds are ultimately not interesting because p_n ~ n log n

[torn escarp]

yeah

[tacit heart]

That’s because log base 1 isn’t defined

[fervent grove]

yes

your response does not make the statement you gave true

I think the correct statement is k^a = k^b (mod n) <=> a = b (mod order of k)

[uncut pumice]

Let $𝑝_𝑖$ be the 𝑖-th prime with $𝑝₁=2, 𝑝₂=3, 𝑝₃=5 ...$,
how do I show for all positive integer 𝑛,
$$
∏_{𝑖=1}ⁿ \frac{𝑝_𝑖}{𝑝_𝑖-1} ≤ 𝑛+1
$$

[sterile pumice]

Mattuwu

[uncut pumice]

I'm trying induction but I got stuck at the induction step

[torn escarp]

I'm guessing something like $\frac{p_i}{p_i-1} = 1+\frac{1}{p_i-1} \le 1+\frac{1}{i}$ from the inequality earlier is useful

[sterile pumice]

Merosity

[torn escarp]

idk maybe not

[uncut pumice]

Ohh, you are totally right, cuz the it telescopes:
$$
∏_{i=1}ⁿ \frac{p_i}{p_i-1}
$$

[sterile pumice]

Mattuwu

[torn escarp]

oh nice

[uncut pumice]

yeah I won't bother typesetting, thanks!

[torn escarp]

yeah you're welcome

[verbal cedar]

i see, thank you! yeah i slightly modified it, and didn't realize that my modification made k3 inconsequential. it was also late at night so i copied the conditions wrong lol, but i was able to get a solution
k1=d+m0-m1
k2=(m1-d)/2
k4=c/2
with the necessary assumptions that k1,d,m0,m1 all have the same parity.

[verbal cedar]

at least, i think lol

[bronze cypress]

Keep unrelated stuff out of the topics channels please... 1 hour mute

[faint dust]

I don't see how the congruence follows from the expansion of (1 + 4k)^2

[torn escarp]

you could put $k=2^su$ with $u=1\mod 2$ and that gets you $$(1+2^{s+2}u)^2 = 1+2^{3+s}u(1+2^{s+1}u)$$ and it kind of makes the induction argument for what to do with powers of $2$ easier since you're getting $$(1+2^kv)^2 = 1+2^{k+1}w$$ for $v=w=1\mod 2$.

[sterile pumice]

Merosity

[torn escarp]

at least, induction is how I'd normally think of trying to prove a more general sort of thing looking at lifting the p-1 roots of unity to mod p^k.

[faint dust]

That makes sense, thank you. I'll try it with other primes p as well

[torn escarp]

p=2 is kind of weird, should be easier and also you can sorta just truncate the binomial theorem I think should be good to see that if w^{p-1}=1 mod p^k then u = w^p satisfies u^{p-1} mod p^{k+1}

[faint dust]

Right, I was trying binomial expansion at first because that seemed to work for odd primes

[torn escarp]

I guess the main sticking point for 2 is $$(1+2n)^2 = 1+8 \frac{n(n+1)}{2}$$

[sterile pumice]

Merosity

[torn escarp]

all odd squares are 1 mod 8

or maybe that doesn't matter, does (a+pn)^p always have this same kind of issue for gcd(a,p)=1? haha

[vast dove]

Dont know which channel to put this

is it true that the above is equal to

[fervent grove]

the first term is O(N^2 * 1/N) = O(N), and the second term is O(N log N)

so yes

it's not too hard to do these computations by just using the integral test for the bounds

[vast dove]

thx

i guess the same reasong shows these two are also equal

[fervent grove]

yes

if you don't see why, you should work it out on paper

[fervent crest]

$\sum_{m>N}\frac{1}{m^2}\leq\sum_{m>N}\frac1{(m-1)m}$

[sterile pumice]

Whoever

[fervent crest]

Second sum is pretty obvious

[sacred junco]

How do i solve question number 4? I tried doing it using induction but it did not work out.

[torn escarp]

you can plug in directly, for instance $$t_{9n+4}=\frac{(9n+4)(9n+4+1)}{2}$$

[sterile pumice]

Merosity

[brisk skiff]

Why is ord$_p(g) = p-1$ always true? (for a prime $p$)

[sterile pumice]

TurkishNutcase

[fervent grove]

this is the definition of what it means for g to be a primitive root (mod p)

[brisk skiff]

right sorry mb lmao thx

[normal sedge]

how do you prove that a primitive root always exists mod p where p is prime?

[west glade]

maybe a bit overkill for p prime but here is a proof for general finite fields https://i.imgur.com/qJcnTdJ.png

[slim vortex]

I'm going through a proof that the ring of gaussian integers Z[i] is euclidean

for a, b in Z[i], I have to verify there exist q, r in Z[i] such that a = qb + r and |r|^2 < |b|^2

the book I'm reading says "It clearly suffices to find q in Z[i] such that |a/b - q| < 1."

and then moves on

I don't see why that clearly suffices 😦

[unkempt void]

Basically just division by b

But yes if |a/b - q| < 1 then take r = a - bq and you can see it is what you want

Since then |r| = |b| |a/b - q|

[slim vortex]

I see it now, thanks!

[unkempt void]

np

[verbal cedar]

feel stupid asking this. but parity (congruence mod 2) is preserved mod n if n is even, but not necessarily when n is odd. i can see why that is, but it seems to be the result of a much more basic/general property of modular arithmetic. would it be something like if a divides b, and x is congruent to y mod a, then z congruent to x mod b implies z congruent to y mod a?

[swift shard]

@verbal cedar
I think you're talking Chinese Remainder Theorem

Oh wait no. You care about the even case hol' up

[verbal cedar]

yeah i thought that was when the modulos are coprime. but I'm more wondering about when one divides the other/they're not coprime

[swift shard]

Indeed CRT doesn't relate

I can explain it using quotient groups, that work?

Basically you can reduce a mod to anything that divides that mod.

We can generalize this to other mods. Anything divisible by 3, in any mod divisible by 3, remains divisible by 3 when reduced.

[leaden swan]

a=kb+r, if c divides b
a=(k(b/c))c+floor(r/c)c+(r mod c) = lc +(r mod c)

So if r were 0 initially,it will end up being 0

[swift shard]

No you've got it backwards. b has to divide a.

Can always reduce the modulo.

x = y (mod a)
x = y + ai for some i

Take both sides by mod b, keeping in mind that b | a,
x = y (mod b)

Keep in mind that doing this loses information about x

[verbal cedar]

hmm. but I'm looking more for the other direction. like i was thinking my original example was a=2 and b=n (n is even). the only thing i care about is the parity of x.
x+kn mod 2=x mod 2
so as long as z is congruent to x mod n, then z has the same parity as x.

but yeah i think we're saying the same thing

[dense scroll]

Does anyone have a hint for the forward direction of d?

[brittle root]

have you tried induction and if so how far have you gotten

[dense scroll]

I was trying to prove it with divisibility and congruence. I’m not sure how I would write out n=1mod3 for the inductive step

[brittle root]

n = 3k+1 for some k

Oh wait nvm ignore that

[dense scroll]

Yeah that doesn’t work

[dusty dragon]

Suppose that 3 | g_n. Then (19 * 10^n - 1)/9 = 3k <=> 19 * 10^n - 1 = 27k. In other words, we require that 19 * 10^n = 1 (mod 27). A quick check shows that this is equivalent to 10^n = 10 (mod 27). Since gcd(10, 27) = 1, Euler's theorem says that 10^{phi(27)} = 1 (mod 27). In other words, 10^18 = 1 (mod 27). This implies that the order of 10 divides 18 and it's not too hard to check that 10^3 = 1 (mod 27). Therefore, 10^{3m} = 1 (mod 27). Therefore, 10^{3m + 1} = 10 (mod 27) which implies that n = 3m + 1 or n = 1 (mod 3)

[verbal cedar]

just a quick question: if i'm talking about something like a mod 2 and b mod 5, then what word would you use for 2 and 5? "modulos"? "moduluses"?

[torn escarp]

modulus is singular and moduli is plural I believe

[verbal cedar]

great, thank you

[torn escarp]

you're welcome

[west glade]

<@&268886789983436800>

[shell minnow]

what happened

[west glade]

spam

[dense scroll]

This makes sense, thank you!

So I'm trying to find integers such that a^2 * x+ b^2 * y = 42. Using the fact that gcd(a^2,b^2) | 42, I've figured out that a,b have to be some combination of 1, 2, 3, 7. I'm not sure how to determine x,y

Ah, so I just brute forced it and found that 9*2 + 4*6 works, but is there a smarter way to find that?

[west glade]

Extended euclidean algorithm

[sacred junco]

Hello. My online friends and I have some (tricky? / interesting?) question and thus are seeking insight.
We are trying to write programs that do such kind of task: Given a positive integer m, compute (and output) 1st term to m-th term of the positive integer sequence S(n), where S(n) is defined by satisfying that the strings of both S(n) and S(n)*2 are consisted of the same set of digits.
Currently, our approaches are basically "brute-force checking": We have computed that S(1) = 10255, however, it takes more than 8 seconds long to compute merely that S(3200) = 4857912 on Ideone.
[Question] Could someone give us some insight of necessary and / or sufficient conditions for a positive integer such that the strings of both it and its double are consisted of the same set of digits?

[west glade]

the only rule that n plays is that S(n) has to be the n'th smallest such number?

problems that depend on the chosen base (so 10 here) often aren't very nice

[sacred junco]

Yes. S(1) = 10255 is the smallest positive integer satisfying that

[drifting imp]

If 4 | (a + b), then a | 4 = 1 and b | 4 = 3

How

[wooden glen]

The two things after "then" don't make sense.

Can you state them in words instead of in symbols?

[drifting imp]

I also thought this

Since a|4 means 4 mod a = 0

Not sure what a|4 = 1 means

[wooden glen]

It must be a typo for "a mod 4 = 1 and b mod 4 = 3, or vice versa".

[drifting imp]

Can you explain why that is

Don't know where the 1 and 3 came from

[wooden glen]

They are the only possibilities for an odd number modulo 4.

And you can try all combinations of which of them each of a and b are, and find that the only ones that make the sum modulo 4 be 0 are that one of a and b is 1 and the other is 3.

[drifting imp]

Couldn't you use something like 7 and 5

[wooden glen]

By definition ".... mod 4" always produces something in {0,1,2,3}.

[drifting imp]

O wait ye I see

How would I start proving this? If 6 | a and 8 | b, then 12 | (a · b)

Only thing I see is 8x6 is 48 and if it divides 48 it also divides 12 maybe

[wooden glen]

Yeah.

[drifting imp]

Can I just multiply two divides together?

Or mods

Not sure how I would write it

a mod 6 = 0 * b mod 8 = 0 ?

[torn escarp]

yeah, x|y means y=xz for some z. So if you also have r|s then s=rt and combining you get xr=yszt so xr|ys

another thing you might want to prove is that if u|v and v|w then u|w

[drifting imp]

Is this good enough ?

Forgive me for the bad hand writing

[torn escarp]

seems fine to me

you could also pull in 9=4*2+1 when you factor the 4 out to get 4(n^2+3n+2) + 1

[dapper topaz]

Do you know what is 2 + 2 ?

[brittle root]

it is clearly 0

oh nevermind the troll left

[native monolith]

2+2 = 5 bro ??????? Idk how u got 0 bro clearly it cant be 0 because 2 > 0 so 2+2 > 0 smh

[brittle root]

sheet ur right

i should immediately quit the mathematical community

[regal ore]

why 2>0 pls proof

[brittle root]

im assuming its a joke but you can use peano arithmetic for this

since 2 = S(1) = S(0) and S(n) > n so

[scarlet idol]

$p > q$ two primes, $a \in \mathbb{N}$, $ a \equiv 1 \mod{q}$, $a \mid pq$ and $q\nmid (p-1)$, then $a = 1$ ?

[sterile pumice]

Espio

[west glade]

yes. a=p would be the only other choice, but then a-1 = 0 mod q, so q | a-1 = p-1 so that doesn't work

oh and I guess a=pq or a=q would be another choice but then a=0 mod q

[drifting imp]

How would i start this

Just know that a,99 are coprime and a,100 are coprime

I also don't see any way to get 6655 from 99 and 100

[patent robin]

Their factors show a connection

[drifting imp]

99 is 11 * 3 * 3, 6655 is 11 * 11 * 11 * 5

Idk after that

[patent robin]

I meant, if 99 = 3² • 11, that means 'a' must not contain those factors (for it to be coprime)

Same with 100 = 2² • 5².

Then we have 6655 = 11³ • 5

Then, definitely 'a' has no common factor with 6655 since that number consists of numbers that 'a' will not have anything to do with.

[drifting imp]

I see

Second part, is it that 101 is prime and 98 is 7^2 * 2. So a must have factors of 101 and 7 but not 2

[dusty dragon]

Well, gcd(a, 100) = 1 implies that 2 is not a factor of a. Furthermore, 98 = 2 * 49 = 2 * 7^2. Therefore, if gcd(a, 98) ≠ 1, then 7 must divide a. Similarly, since gcd(a, 101) ≠ 1 and 101 is prime, 101 must divide a. Since gcd(7, 101) = 1, then a must have factors, 101 and 7 implying that a must have a factor of 101 * 7 > 100 * 7 = 700. Therefore, a > 700

[drifting imp]

This is what I said right

[dusty dragon]

Yes just a bit fleshed out

[woven oracle]

2 + 2 = 0 mod 4 😎

[sacred junco]

So, I was solving this particular puzzle, and the answer I got was 105263157894736842, which seems to be correct.
Then I tried doing a different variation where 3(n1 n2 ... nk-1 nk)=(nk n1 n2 ..... nk-1),essentially the same question but with 3x instead of 2x,
I found the answer to be 1034482758620689655172413793, which weirdly enough was the recurring digits of 3/29. Any ideas as to why this correlation showed up out of nowhere?

[sacred junco]

btw the answer has exactly 29 digits

[west glade]

well the first number are the digits of 1/95. in general I'm not surprised that you end up with the digits of some repeating decimal

cause well they exactly satisfy that if you take a multiple of them then you get a rotation of the digits

why 1/95 and 3/29 in particular? no clue

[sacred junco]

yeah

[west glade]

95 is surprisingly high but 29 isn't that big if you consider the extra constraints that you need that it has to be specifically only one rotation

[sacred junco]

i think it's 9.5 to be exact, since 1/95 skips one 0 after the decimal point

but 3/29 was just screaming out, because well, 3n and 29 digits

maybe just a coincidence

[west glade]

well quite often will 1/n have n repeating digits

something something primitive root

I think the 3 is here more because 3/29 is bigger than 0.1

it's very likely that your number starts with a 1 if it is the smallest

[west glade]

yes good point

[sacred junco]

which'll be 2/19

19 digits

[west glade]

uhm I meant n-1 repeating digits. but same thing

if n is prime then the possible repeats is a divisor of n-1

[sacred junco]

ohh

[west glade]

you can work out how it relates to the powers 10^k mod n

[west glade]

ah yes 19 is much smaller. way better

would be interesting if the next is 4/39

39 isn't prime tho so that might ruin it

4/39 = 0.102564... and 102564 indeed works for 4*n. but not sure if it's the smallest

5/49 also works for 5*n. 42 digits this time. so yeah there is definitely a pattern

[west glade]

(in general its a divisor of phi(n))

[sacred junco]

i had no idea this pattern actually was a thing

https://en.wikipedia.org/wiki/Parasitic_number

just checked

had a hunch

[west glade]

figured that somebody else already did that

[sacred junco]

so the pattern to find such numbers is essentially:
a/(n*10-1)

where a can go from a=n to a=(n*10-1)

[brazen python]

Hello

I don't understand how m and n being coprime leads to a being a multiple of n

[brittle root]

suppose alpha is not a multiple of n then

[brazen python]

if alpha is not a multiple of n then m and n are not coprime

[brittle root]

well there is a faster (albeit unrigorous way) to see it

[brazen python]

yes pls

[brittle root]

theres no way to make beta copies of n without having some km

because m and n are coprime

if alpha is not a multiple of n alpha < n

suppose WLOG n < m

do you see whats wrong

[dusty dragon]

The result is a generalisation of Euclid’s lemma

[brazen python]

no, sry

[brittle root]

alpha m = beta n

since we wlog n < m and we said for contradiction alpha is not a multiple of n

to have them being equal

ok you know im making this overcomplicated sorry

just divide

alpha m / n = beta

the left side is clearly not an integer

[brittle root]

my apologies, we dont even need this WLOG

[brazen python]

this makes sense

so since beta is not an integer, alpha (integer) must be a multiple of n?

[dusty dragon]

Use the fact that m and n are coprime

Therefore, if alpha * m/n is an integer, then alpha/n is an integer

[brazen python]

ohhh

ok i see now

ty!

[brittle root]

^^ this is a lot cleaner than mine

nice and unnecessary contradiction I created lmfao

i should probably sleep i am literally sick

[dusty dragon]

get well soon!

I should probably sleep soon too lol

Its 1:44am here

[brittle root]

ty!

[covert finch]

if you know 7^10 = 24 or -1 mod 25, is there an easy way to evaluate 7^9 mod 25 based on that fact?

[fervent grove]

I mean 7^2 = -1 (mod 25), which should make the computation doable

[covert finch]

oh true lol

[still flare]

You know that $7^9 = (7^2)^4 \times 7^1$. Use this fact.

[sterile pumice]

Boytjie

[covert finch]

yea yea

[dusty dragon]

If you want to use the fact that 7^{10} = -1 (mod 25), then note that 7^9 = 7^{10} * 7^{-1} = -1 * 18 (mod 25) = 7

[tacit heart]

An integer $n$ can satisfy the equation $n=x^2+y^2$ where $x,y \in \mathbb{Z} $\iff$ every prime $p \equiv 3 \pmod{4}$ that divides $n$ occurs in $n$’s prime factorization with an even exponent.

[sterile pumice]

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

[tacit heart]

Why is this true?

[stiff rivet]

this is called the sum of squares theorem, im sure you can find a proof if you google that

[tacit heart]

Oh thanks

[sacred junco]

Thank you for your help.

[torn escarp]

you're welcome

[analog onyx]

at this point i should apply the fact that p is prime

but i dont really know what that does for me

like what is the next step since p is prime

[brittle root]

mn/p = k

[analog onyx]

maybe p divides mn

[brittle root]

k is an integer

[dusty dragon]

When you get a problem where they ask you to show "x or y", one strategy you can employ is to assume that x doesn't hold and show that y must hold true

[brittle root]

so mn/p is an integer

the result immediately follows

[analog onyx]

but since p is prime, it either divides one or the other or both of m and n

gotcha okay

[dusty dragon]

So here, we know that p | mn. Let's suppose that p does not divide m. What you now want to show is that p | n

[brittle root]

(all good I covered it)

[analog onyx]

so then if p | c^2

p | c*c

and then by the previous problem we know that p | c

[dusty dragon]

yes

[analog onyx]

gotcha okay

[dusty dragon]

that's a direct corollary of the problem you proved

(it might be useful to think about why p is required to be prime)

[analog onyx]

uh well the problems before were working with relatively prime numbers

i think its all building upon itself

[dusty dragon]

ah the relatively prime version is a generalisation of this

[analog onyx]

feel like the order of them is methodical

maybe except for the set stuff at the top

[brittle root]

1.4 proof: trivial

[dusty dragon]

the proof for 1.3 feels like it's missing steps lmao

I don't see how k = mn/p is an integer immediately implies p | m or p | n using the fact that p is prime

I mean, it's true but that's what you want to prove

[analog onyx]

since p is prime and it divides a product of numbers

it must divide either one of those numbers

like it makes sense to me

[dusty dragon]

that's what you want to prove

[analog onyx]

but i dont know how to explain it

[dusty dragon]

you've basically used what you want to prove to prove it

[analog onyx]

its one of those things that is trivial but idk how to describe what needs to be done to show it

yeah i see your point

what would you recommend

[dusty dragon]

have you seen the fundamental theorem of arithmetic?

[analog onyx]

every number can be written into a prime factorization

[dusty dragon]

yup, so since p | mn, what can you say about the prime factorisation of mn

[analog onyx]

so mn's prime factorization but have something divisible by p

[dusty dragon]

yeah so one of the primes must be p. Now what you can do is to decompose m and n into their prime factorisations as well

Let $m = p_1^{a_1} p_2^{a_2} \dots p_{k}^{a_{k}}$ and $n = q_1^{b_1} q_2^{b_2} \dots q_{\ell}^{b_{\ell}}$. Then $mn = \left(p_1^{a_1} p_2^{a_2} \dots p_{k}^{a_{k}}\right) \left(q_1^{b_1} q_2^{b_2} \dots q_{\ell}^{b_{\ell}}\right)$

[analog onyx]

well like okay but

since p divides mn, we know that p exists in the prime factorization of either m or n

so then im done

[dusty dragon]

yeah that's the basic idea

[analog onyx]

or is that not rigourous enough

[dusty dragon]

p must appear in the prime factorisation in either m or n (or both)

[analog onyx]

yes

[dusty dragon]

we just need to get to that conclusion

[analog onyx]

the way youre showing it seems overkill for the proof of this though, as in the level of it

compared to everything else

im glad youre showing it to me but i dont think that level is my expectation if that makes sense

[dusty dragon]

it's actually not that overkill

you just look at each prime factorisation

and the conclusion falls out directly from FTA

there are other elementary ways using bezout's lemma

you could also argue by contradiction

[analog onyx]

im familiar with that

[dusty dragon]

assume that p does not divide m or n

and arrive at a contradiction

[analog onyx]

this is going to require bezouts lemma?

[dusty dragon]

ok here's a more elementary proof.
Suppose that p | mn and p does not divide m. We will show that p | n. Since p does not divide m, then gcd(p, m) = 1 and so there exist integers a, b such that ap + bm = 1 (this is Bezout's lemma). Multiplying both sides by n, we have that n = (ap)n + bmn. But since p | mn, we can write mn = pk to get n = (an)p + (bk)p = p[an + bk]. But this implies that p | n.

[analog onyx]

that seems really similar to my proof of euclids lemma

[dusty dragon]

this is euclid's lemma

[analog onyx]

Lemma 1 was bezouts identity

ax+by = gcd(a,b)

[dusty dragon]

yeah, this is an alternative formulation of euclid's lemma

[analog onyx]

the one i have written here or 1.3

[dusty dragon]

both

they are equivalent

(Lemma 2) <=> (1.3) and the proof for either follows pretty much the same way

[analog onyx]

okay

and we can assume p does not divide m without loss of generality right

[dusty dragon]

yes

[analog onyx]

so it doesnt matter which way we assume p doesnt divide

okay

[dusty dragon]

the argument is symmetric

[analog onyx]

i think the first way with the prime factorizaiton makes the most sense intuitvely

but i like this proof better its more elementary and similar to what ive done before

[dusty dragon]

it's nice to have different proofs in mind when you encounter a result

and depending on what you've been taught, you can sorta hack your way to the result using results you've already proven/seen

i.e. if you've never seen bezout's lemma, it might be hard to just suddenly use it in the proof of euclid's lemma

[analog onyx]

i havnt taken a formula NT course

just an intro to proof course where we learned the different techniques and how to write a little but

but the content was all over the place in terms of the proofs

but ive worked with bezouts identity on my capstone project i did on diophantine equations

for 1.5, im doing by contradiction

ive gotten to the point where s^2p = r^2

and so p | r^2 and hence p | r by the previous problem

just not sure where this contradiction comes in, maybe with p | s

wait

[dusty dragon]

yup that's right so far

so p | r, use the definition of | to re-express r in terms of p

[analog onyx]

yeah thats why i said wait

[dusty dragon]

also you may assume that r and s are relatively prime; otherwise, just keep dividing by their common factor

[analog onyx]

pt=r

i did

thats where the contradiction normally comes from

from my experience

[dusty dragon]

yeah that's right

[dusty dragon]

once you have this, you basically have the contradiction

[analog onyx]

i dont see it yet

how does that imply r and s arent in lowest terms

[dusty dragon]

here are the pieces of information you have right now:

1. r and s are relatively prime.
2. pt = r
3. s^2p = r^2

[analog onyx]

duh okay

[dusty dragon]

what's the most natural progression you can make using these three pieces of information?

[analog onyx]

well its obvious now

[dusty dragon]

👍

[analog onyx]

if i went back and looked at what i have previously wrote

i feel like im so close to being able to do these on my own but im always missing something subtle and then obvious once pointed out

[dusty dragon]

takes practice

it's very common for students starting out to tunnel vision themselves into getting stuck

and the more practice you do, the better you'll get at picking up what information you have that's relevant

[analog onyx]

this is gonna lead me to p | s right

[dusty dragon]

yup

[analog onyx]

which is a contradiction since gcd(r,s)=1

[dusty dragon]

nice!

[analog onyx]

i have like p^2t^2 = ps^2

so pt^2 = s^2

and then apply the previous problem since p | s^2.

[dusty dragon]

👍

[analog onyx]

is there any special way to write a composite number

like for rationals we write r/s where s/=0

[dusty dragon]

n = ab where 1 < a, b < n

[analog onyx]

or is composite just like prime where we cant express it any special way

[loud maple]

One could write a composite number as n=pq where neither p nor q is 1

[analog onyx]

okay i can buy that

[loud maple]

What is a capstone project?

Is it a research paper you published?

[analog onyx]

it was just like a research project

it wasnt a requirement to get published but mine is in the process of being published i hope

[loud maple]

Nice, so you have proved new theorems?

[analog onyx]

it was sent to a journal i guess were still waiting on it to be reviewed

i mean i guess theyre new, wouldnt be much worth publication otherwise i suppose

[dusty dragon]

that's pretty impressive

[analog onyx]

its gonna be trivial to you i feel like

but it was fun to do

i feel like i really understand it, i loved presenting about it because ive worked with it for so long it makes perfect sense to me now

i wrote a python program to apply the algorithm as well

[dusty dragon]

one of my current research projects is to find potentially new results to the union-closed sets conjecture, perhaps proving the conjecture for other families of sets

[loud maple]

How can something be both trivial and worth publishing?

[analog onyx]

well worth publishing and trivial are subjective person to person anyway

like maybe to someone this method is obvious and not worth publication i suppose

i just feel like theres plenty of people that couldve came up with this

i could be being humble but i doubt it since im sitting here getting help with elementary number theory lol

[loud maple]

But you came up with it first

So that is nice

[analog onyx]

well like i said

someone probably know this works and its so obvious to them they never thought twice ab it

but i guess so, yeah

if either of you read it, let me know what you think or if you have any feedback

[dusty dragon]

a lot of things are 'obvious' in retrospect

[analog onyx]

the professor i worked on it with has sent it off for review but we havnt heard anything

id like some feedback on it though

[analog onyx]

yes like the whole thing is trivial to me now lol

[dusty dragon]

i'll have a look at it when i'm free

[analog onyx]

feel free to tag or dm me whenever youre done with it

if either of you are interested in the program i can send that as well, i had so much fun writing that lol

[coarse carbon]

How do we solve this without the modular exponentiation

[dusty dragon]

The last two can be done quite easily since gcd(157, 253) = gcd(28, 253) = 1, so you can appeal to Euler’s theorem to simplify the power. The first one is a bit more fiddly and I can’t really think of a way that’s faster than just brute forcing all powers of 66 (mod 253)

[coarse carbon]

But the power is smaller than 220 which is euler’s indicator

[torn escarp]

since 5=2+3 you can immediately say 253=11*23 so maybe it's simple to do with the CRT

caus 66=0 mod 11

[sudden swift]

does lcm distribute over gcd?

[stiff rivet]

consider prime factorizations

[sudden swift]

i guess they're sort of like union and intersection

of prime factorisations as multisets

[stiff rivet]

it reduces to case of whether min/max distributes over max/min

(which should both be true)

[sudden swift]

hm

so gcd also distributes over lcm

interesting

[fierce nymph]

are you thinking about the information theoretic approach?

[dusty dragon]

I’ve been considering perhaps slightly more elementary means, trying to characterise the lattice of a union-closed family of sets and perhaps saying something meaningful about that

Clearly any family of sets that have a “long enough” chain satisfies the conjecture

[fierce nymph]

I see, I ask because there was a lot of hype online recently after the quanta article

[dusty dragon]

So I’m considering looking at families whose chains are not long enough

[dusty dragon]

Yeah that was a pretty nice read, some interesting insight into the lower bounds

[fierce nymph]

seems like maybe the approach is stuck at .38, so perhaps new ideas are needed to get to 0.5

[dusty dragon]

I’ve thought of something interesting and I’m going to bring it up with my supervisor to maybe flesh out some of the groundwork of it

If my ideas are correct, then it might be possible to flesh it out to a full proof

[fierce nymph]

oh nice, are you a phd student?

[dusty dragon]

Nope, undergrad but I’m in my honours year which is effectively a year-long research year

[fierce nymph]

that would certainly make you famous if you managed to prove it!

dangerous problem to work on though, gets stuck in your head and you feel compelled to throw hours at it

[dusty dragon]

That’s what’s been happening to me hahaha

I’ve spent a few days in a row thinking about the problem

[fierce nymph]

that was my fav quote from the quanta article, when Mike Saks was like "please don't make me think about this problem again"

that's the sound of someone who has lost some significant time to it hah

[sleek spire]

what are some strats to solving diophantine equations

[torn escarp]

check out this has some strategies https://cs.uwaterloo.ca/~cbruni/pdfs/Techniques of Diophantine Equations.pdf

[sleek spire]

lol I read the first thing and it sounded promising

then it started doing some modular form stuff which was just like

besides the point

I want some elementary strategies

[torn escarp]

one sort of common trick, idk if it's in there or not, is if you have ab=c^n and you can show gcd(a,b)=1 then a=ux^n and b=vy^n with units so that uv=1

and you can sorta alter this slightly

[sleek spire]

mh

are there any tricks for diophantine equations in 3 variables

[torn escarp]

do you have a specific diophantine equation you're wanting to solve right now

[sleek spire]

I'm trying the no solution one right now

[sleek spire]

yes

[torn escarp]

which one, post it here

[sleek spire]

,, x^2 + y^2 + z^2 - xy - yz - zx = 3

[torn escarp]

showing something has no solutions tends to be easier

[sleek spire]

yeah

wait

let me check wolframalpha

[torn escarp]

like seeing a square and 3 and three terms makes me think look mod 2, 4, 3 or 9

[sleek spire]

okay yeah lol

[sleek spire]

I'll try Z4

or wait

Z9

[sour rivet]

Hey, I was taking number theory a couple years ago and there was this thing that looked like a fraction but it wasn't a fraction. Anyone know what that might be?

it was used for I think... solving modular systems of equations or something?

[sleek spire]

can you draw it?

[torn escarp]

legendre symbol maybe

[sour rivet]

that's it merosity, thank you

[torn escarp]

you're welcome

[sour rivet]

residues, it's all coming back lol

[torn escarp]

cool 😎

[torn escarp]

2, 4, 3, 9 won't work (I just brute forced it on computer)

[sleek spire]

how did you brute force it?

[torn escarp]

three nested for loops

[sleek spire]

oh

lmao

[torn escarp]

lol

[sleek spire]

put another for loop around it to see what works

[torn escarp]

looks like nothing up to 10, actually thinking there's probably always a solution

if I recall correctly, if you check a quadratic in 3 variables mod 8, then it automatically has a solution mod p^n for all n

there might be some slight caveats that I'm not considering but effectively quadratics mod p when p !=2 have no problem hensel lifting, at least when they're homogeneous, but I think when they're not we can just diagonalize them anyways to make them a quadratic form

[sleek spire]

are you sure 2 doesn't work

[torn escarp]

reducing mod 2 you have two kinds of solutions, two even one odd or one even and two odd

[sleek spire]

ah wait I forgot to do modulo in my program

lmao

[torn escarp]

basically the reason this won't work is Hasse-Minkowski local-global theorem for quadratic forms is in our way

this has rational solutions, so it has a solution mod n for all n

[sleek spire]

ah

[regal ore]

Multiply both sides by 2
LHS becomes
(x-y)^2 + (y-z)^2 + (z-x)^2

[torn escarp]

so basically wolfram alpha was just wrong lol

[sleek spire]

so one of them is 4 and the other ones are 1

then it's just a linear system

right

ok thanks

ok well all of those linear systems are inconsistent

so it has no solution

(checked using rouche capelli)

[regal ore]

Don't forget the negatives btw

[sleek spire]

right

[torn escarp]

no they're linearly dependent, not inconsistent, you have an infinite family of solutions

x=n-1, y=n, z=n+1 all workd

set n=0 or n=1 to see the simplest solutions work out

[sleek spire]

yeah I wasn't considering negatives

[torn escarp]

negatives have nothing to do with it, x=1, y=2, z=3 works just fine

[sleek spire]

then y - z is negative

that's what I meant basically I was only checking for the differences being positive

sorry if I wasn't clear

[torn escarp]

oh I see what you meant now, my bad

[analog onyx]

Any other way to do this? maybe by contradiction?

I dont think this is right looking at it again since I assumed p | n

The wording made me think that was given to me but rereading it again I don't think so

[torn escarp]

I think you can reword it slightly to say because it's composite there's some p which divides n

also if p|a it doesn't mean p < a could be p=a though so probably should have p <= a

I don't think that breaks anything, but I'm not looking too close either

[analog onyx]

by the fundamental theorem of arithmetic right?

[torn escarp]

well I'm just going by definition of composite integer

[analog onyx]

my professor was showing me another way to show this result without using the increasing property of the square root function

and i liked his way better but I cant remember it

[torn escarp]

but you could say that I guess too to be safe

[torn escarp]

I feel like I've seen a better way too, I'll try to remember or come up with one too, sounds fun

I'm thinking something roughly like, take a divisor d, if its <= sqrt(n) you're basically done, otherwise look at n/d and that's <= sqrt(n)

[analog onyx]

i think it was something like that

[fervent grove]

isn't this basically the same proof, once you label a = min{d,n/d}

[analog onyx]

oh here wait

it was like assume a > sqrt(n) and b > sqrt(n)

then ab > n which isnt true obv

[torn escarp]

yeah, probably

[analog onyx]

so then either a <= sqrt(n) and or b <= sqrt(n)

just gonna pick the case of a <= sqrt(n), then there exists a prime p such that p | a, and so p <= a <= sqrt(n)

so then p | ab, or p | n

does that work?

[regal ore]

As n is composite hence there exist prime q and integer k >= 2 that n = qk. Let p be minimum such q and let m be the resulting value of k
all prime factors of m are more than or equal to p so n = pm >= p^2 hence p <= sqrt(n)

[analog onyx]

p is the minimum of q?

[regal ore]

q is any prime divisible by n. Let p be the one with lowest value

[analog onyx]

what do you think of the outline of the proof i typed where i assumed a,b >= sqrt(n)?

[native monolith]

So I know this means $n^2-5\equiv 0 \mod{p}$ ie. $5$ is a QR mod p. So then you use QRL but I can't figure out the last trick. Showing $1=(\frac{p}{5})(-1)^{\frac{p-1}{2}}$ if and only if $p\equiv \pm 1 \mod{5}$ without using a really long winded method (testing for each value mod 5)

[sterile pumice]

Max..

[lusty dew]

not sure if this is the right channel but i dont get how option two is correct, wouldn't the cos part of the equation not cancel out due to the constants of the two being reciprocals of each other?

[loud maple]

'constants' as in?

[lusty dew]

Like this

[native monolith]

I mean it's not the right channel this is more #calculus or #real-complex-analysis
dw about that tho

$$e^{iz}=cos(z)+isin(z)$$ $$e^{-iz}=cos(z)-isin(z)$$ In the second we have used the fact $cos(z)=cos(-z)$ and $sin(z)=-sin(-z)$. Subtract $e^{-iz}$ from $e^{iz}$ and we get $e^{iz}-e^{-iz}=2isin(z)$

[sterile pumice]

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

[brittle root]

that wouldnt be real analysis

#prealg-and-algebra seems more appropriate

[torn escarp]

you can use quadratic reciprocity directly, $$1=\left(\frac{5}{p}\right) = (-1)^{\frac{p-1}{2}\frac{5-1}{2}} \left(\frac{p}{5}\right) =\left(\frac{p}{5}\right)$$

[sterile pumice]

Merosity

[torn escarp]

since p is a QR, it means it can only be +-1 mod 5

I think you just missed the extra exponent

the way I think of it is really just to flip the sign if both primes are 3 mod 4, otherwise it's exactly the same. So as long as one of the primes is 1 mod 4, you don't have to worry what the other prime is mod 4

[sleek spire]

(QR?)

[torn escarp]

for what it's worth, I only ever really remembered this after proving QR several times over the course of my life and it just eventually stuck when proving by gauss sums and seeing the -1 comes from a (-1/p) legendre symbol to a power which is literally (-1)^((p-1)/2) as well

[torn escarp]

quadratic residue

[sleek spire]

ah

[torn escarp]

also NR usually stands for nonresidue

[brisk skiff]

Just to double check:

the numbers in the system $4\mathbb{Z}_{12}$ are $0$, $4$, and $8$, right?

[sterile pumice]

TurkishNutcase

[brittle root]

is Z_12 = {0, 1, 2, ... , 11}

under addition mod 12

[still flare]

This depends on how you define it exactly. When you see quotient groups, you will define it differently. However for now this is an adequate definition.

[brisk skiff]

yeah

[brittle root]

assuming you define 4Z_12 as {4n mod 12 | n in Z_12} then yes

[brisk skiff]

alright so if we have the algebraic property '' If $2x =0$, then $x=0$ '', this system wouldn't satisfy that correct? Because $2$ does not even exist in that system

[sterile pumice]

TurkishNutcase

[fervent crest]

Well 2x can also be interpreted as x + x

[drifting imp]

Maybe split it into (n+5)(n-5) ?

[brisk skiff]

oh yeah...thx

[blissful vessel]

how can i show that for some prime $p$, that the product $(p - k)(p - j)$ for some $k,j \in \mathbb{N}_{>0}$ is not divisible by $p$?

[sterile pumice]

MarkusG

[fervent crest]

I mean just choose k=j=1 then it works for any prime p?

Oh it just never divides

[blissful vessel]

yeah

unless k or j is equal to 1 or p

i'm just looking for a proof of that

[fervent crest]

Well remember two facts: if a prime divides a product then it divides one of the factor in the product, then if p is a prime and 1<i<p then i does not divide p

[blissful vessel]

is there a proof for the second part

[fervent crest]

It’s the definition of prime

[blissful vessel]

i'm being required to do number theory without any prior knowledge of number theory 😔

oh ok neat

[sacred junco]

Let $a,b \in \mathbb{N}$ and $\bar{Q}(n)$ be the iterated digit sum function, meaning that the digit sum is repeatedly taken until only one digit remains. For example, $\ \bar{Q}(1516)=4 \$ How can I show that $\ \bar{Q}(a+b)=\bar{Q}\left( \bar{Q}(a)+ \bar{Q}(b) \right)\$ Is this true for all numbers? At least for all numbers I have tried, it seems to hold.

[sterile pumice]

Plazzi

[loud maple]

the function in question preserves the remainder modulo 9, and takes values in the set {1,2,...,9}

From here it is trivial to prove the required result.

[sacred junco]

Got it thanks

[scenic onyx]

.

[native monolith]

Ah yes thank you, I forgot the powers were multiplied not added 🤭 ty

[verbal cedar]

stupid modular arithmetic question... if x mod 4=y, will x mod 2=y mod 2?

[brittle root]

there are 4 cases to check yeah?

(im sure theres a more clever way but)

0 mod 4 = 0 yes
1 mod 4 = 1 yes
2 mod 4 = 2 yes
3 mod 4 = 3 yes

[dusty dragon]

Suppose that y = x (mod 4). Then we can write y = 4k + x for some integer k. But note that this is equivalent to y = 2(2k) + x

[verbal cedar]

my brain is so fried by this problem i can't believe i didn't even think to just check all the cases lmfao.
thank god it's true, i might be able to salvage all this work with a few minor adjustments from mod 2 to mod 4...

[verbal cedar]

or that. how did i not see something so obvious...? lmao stupid question confirmed

thank you both ❤️

[brittle root]

this is better, thank you

[sleek spire]

how do I derive the discriminant formula for cubics?

I suppose using vieta but I'm not sure how I'd do it

[stiff rivet]

what is your notion of discriminant?

[sleek spire]

,, \prod_{i < j} (\alpha_i - \alpha_j)^2

where alpha_n are the roots

how do I show that this is equivalent to the formula that uses the polynomial's coefficients

[stiff rivet]

eh, its very annoying i think

you reduce to the case of the depressed cubic and use some properties of symmetric polynomials

[opal obsidian]

why is the prime factorization of natural numbers not completely proven?

[stiff rivet]

what?

[eternal wraith]

if gcd of (a,b) = d then there exists x,y such that ax + by = d

how do i find the x and y?

[torn escarp]

the process is called the extended euclidean algorithm

in short, it's just the regular euclidean algorithm, but you keep track of what you do at each step of the way down to get a bunch of things to substitute in

[eternal wraith]

okay so that makes sense

how do i find all possible answers after ive found one

[torn escarp]

that's easy since you just need to solve ax+by=0, which has the simple solution of x=b, y=-a

every integer multiple of this added to your single solution will be a solution

[wild summit]

ah nice

[sleek spire]

uh

basically

I have to calculate the discriminant of some random polynomial for my algebra homework

and the roots take up 2 lines each in wolframalpha

[stiff rivet]

use a CAS

[sleek spire]

and then copy paste the result as latex?

these are the roots fwiw

[stiff rivet]

i mean you have the coefficients, you can compute the discriminant in terms of that

thats like the whole point of the thing

[sleek spire]

yeah but I don't think my ta will be ok with me doing that without proving the equivalence

[eternal wraith]

Sorry for the late reply, but how do we know that this will cover all possible solutions and not just some of them?

[opal obsidian]

sorry I just got confused. It is, but there isn't an algorithm for it (or atleast not yet?).

[west glade]

not an efficient algorithm

there is an algorithm. just check every number. but that clearly takes ages

(and of course there are smarter approaches. but nothing fast)

[unkempt void]

Proving the equivalence will still be faster tbf

I can't imagine a prof wanting you to actually compute w these roots right bruh

[dark maple]

I got all numbers from 1 to 100, but one number is missing. What is the fastest way to find that number?

[brittle root]

I'd add them all up

you know what the sum from 1 to 100 is right

[umbral bridge]

5050 - (sum of numbers you have) = number you want

If these numbers are on computers then you can use hash maps but it'd be the same time complexity as summing the numbers you have

[sleek geode]

Hello everyone

I'm interested in solving this problem

https://www.quora.com/In-the-six-digit-number-1VWXYZ-each-letter-represents-a-digit-Given-that-1VWXYZ-3-VWXYZ1-How-do-you-prove-that-V-W-X-Y-Z-26

But instead of finding the exact number, I want to find the sum directly

Let A=1vwxyz, A'=vwxyz1, S the sum digit (for both of them)
Since A'=3A, it is divided by 3 thus S is divided of 3
That implies also A is divided by 3 due to them sharing the same digit
So A' is divided by 9, implying again S is divided by 9.
First note that from the given, we can clearly see v≥3 and z=7
From this 11≤S≤46
Finally we have 3 candidate for S {18, 27, 36} (obviously we can't take 45 since that means A'=999991)

I'm stuck here, and can't deduce it further. What do you guys think ?

[analog onyx]

,rotate

[analog onyx]

for 1.3, can’t i just say something like First, suppose that p | mn, if p | m we’re done. Now, suppose that p does not divide m ….

i was just missing the fact that if p | m it’s obvious and we’re done

[dusty dragon]

Yes

If p | m, then there’s nothing else to prove

[analog onyx]

thats what i figured, thanks

how would you would that if you were writing the proof? i don't necessarily like the way i worded it

[dusty dragon]

I think it’s fine the way that you’ve written it

[analog onyx]

okay thanks

[dusty dragon]

I’d probably do:
Suppose that p | mn. If p | m, then we’re done. We may now assume that p does not divide m.

[analog onyx]

i like that

[pine badge]

How do you prove that if the gcd(a,b) = 1 and c divides a, then gcd(c,b) = 1.
I understand that since a and b share no divisors other than 1, so unless a=0 c<a c can't have any divisors that a didn't have.

[brittle root]

your understanding is correct

the proof does follow quite directly

alternatively try contradiction and it also follows quickly

[pine badge]

What do you mean by follows directly?

Oh that's it lol

If gcd(c,b) did not equal 1, then gcd(a,b) =1 would be a contradiction.

I guess I was trying to show this with equations
d = ax + by and a = c*a1

[brittle root]

just fill in the details

[pine badge]

So, then gcd(c*a1,b) = 1 how can I get rid of a1?

[brittle root]

you know that gcd(a1, b)=1 too

so then it follows directly

[torn escarp]

how? that's what you have to prove

[brittle root]

as in

it follows

because a1 is a factor of a so its also coprime to b

well