A proof about Automorphism in congruence class [on hold]

Suppose gcd(m,n)=1, and let $ F :Z_n→Z_n$ be defined by $ F([a])=m[a]$ . Prove that $ F$ is an automorphism of the additive group $ Z_n$ . I find it is diffcult to prove $ F$ is injective and surjective. Could you please to help me proof it with all the details. I type it roughly, and i am sorry and sincerely looking for a result.

Is 2(2^(p) − 1) a divisor of n? How about 2^2(2^(p − 1))? Finish the proof.

A positive integer is called whole if it equals the sum of its positive divisors.

Example: 6 is whole because the divisors of 6are 1,2 and 3 and 6=1+2+3.

Show that 28 is whole.

We want to show that the number n = 2^(p−1)(2^(p) − 1) is a whole number when 2^(p) − 1 is prime.

What are the divisors of 2^(p−1)? (it might help to try various values: what are the divisors of 2^3 or 2^4…?)

What is their sum? Hint: 1+2+2^2 +…2^k =2^(k+1) −1(geometric series)

Is 2(2p − 1) a divisor of n? How about 22(2p − 1)? Finish the proof.

Proof by mathematical induction with the problem 40(2n)! ≥ 30^n

I want to start by saying that I have for less trouble handling a non-inequality induction problem. I really don’t understand the steps to take to get to the desired end product with these inequality induction proofs. That being said, I feel like I just wrote a mess on my paper that leads me nowhere. Here’s my proof so far for the mathematical induction of $ 40(2n)!≥30^{n}$ , where n ≥ 1

Let P(n) be the statement $ 40(2n)!≥30^{n}$ where n ≥ 1.

Basis Step: $ LHS = 40 * 2! = 80$ and $ RHS = 30^{1} = 30$

$ 80 ≥ 30$

Inductive Step: Assume $ P(k)$ is true for $ k = 1$ . Our goal is to show $ P(k+1)$ is true by showing $ 40(2(k+1))!≥30^{k+1}$ for $ k ≥ 1$ .

(Beyond this step I have no clue how to alter the LHS factorial or the RHS exponent in such a way to benefit me. Below is my work so far)

LHS: (I tried to add $ (2k+2)(2k+1)$ to both sides, but then I didn’t see how that would help)$ 40(2k)!≥30^{k} = (2k)!*40≥30^{k} = (2k+2)(2k+1)(2k)!*40≥30^{k}*(2k+2)(2k+1)$

RHS: $ 40(2(k+1))!≥30^{k+1}=(2k+2)!*40≥30^{k+1}=(2k+2)(2k+1)(2k)!*40≥30^{k+1}$ $ =(2k+2)(2k+1)(2k)!*40≥30*30^{k}$

(I then assumed the inductive hypothesis and placed $ 40(2k)!≥30^{k}$ in the middle to get…)

$ (2k+2)(2k+1)(2k)!*40≥40(2k)!≥30^{k}≥30*30^{k}$

At this point, I’ve got nothing. I know that $ 30^{k}≥30*30^{k}$ makes no sense, but I don’t know where to move $ 30*30^{k}$ since I can’t assume that $ 40(2k)!≥30*30^{k}$ . I don’t have any clue how I can manipulate either side to help me.

Alternative proof of the fact that heapify can be linear-time

As an exercise, I’m trying to prove by myself that constructing a binary heap from an array in-place can be $ O(N)$ . I’ve come up with an idea, but I’m not sure about its correctness.

Firstly, I define the following procedure (pseudocode):

process_node():     if the node has children:         select the child node with the maximum value         if the selected node's value is greater than the value of current node:             swap current node with the selected node 

Then I run this procedure on all non-leaf nodes going down level by level in the binary tree view of the array. So the root is processed first, then comes the first level etc. After doing this, a half of leaf nodes become smaller than all of their ancestors. Another run of the procedure on the same nodes settles the other half of the leaves. Thus, they have been put in place in the heap and can be removed from the processing.

The number of leaves is halved, and so is the number of non-leaf nodes. The procedure is run again on new non-leaves, and the process is repeated until all the elements of the array are processed.

The number of nodes on which the procedure is run starts with $ N/2$ and later is halved. We get a decreasing geometric series with the sum being $ O(N)$ .

Are there any mistakes in my reasoning?

Is $H_{n+t}(D^n \times F, S^{n-1} \times F) \cong H_t(F)$? Proof of Suspension Isomorphism.

Here we let $ F$ be a CW complex. $ D^n, S^{n-1}$ be the disk and sphere respectively. Is it true that

$ H_{n+t}(D^n \times F, S^{n-1} \times F) \cong H_t(F)$ for all $ t$ ?

Here $ H_*$ is ordinary singular homology theory.


My progress for why the equation holds $ k=\Bbb Z$ or $ \Bbb Z /2 \Bbb Z$

We ompute $ $ H_{n+t}(D^n \times F;k), \quad H_{n+t-1}(S^{n-1} \times F;k)$ $ This follows from Kunneth Formula. $ $ 0 \rightarrow \bigoplus (H_i(X;k) \otimes H_{s-i}(Y;k) ) \rightarrow H_s(X \times Y) \rightarrow \bigoplus_i Tor_R(H_i(X,k) , H_{s-i-1}(Y,k) \rightarrow 0 $ $ As our choice of $ k$ and $ Y=D^n$ or $ S^{n-1}$ , implies there are no torsion terms. Thus we obtain $ $ H_{n+t}(D^n \times F;k) \cong H_{n+t}(F), \text{ and } H_{n+t-1} (S^{n-1} \times F;k )\cong h_t(F)$ $

Our long exact sequence looks like, $ $ h_{t-1}(F) \rightarrow h_{n+t}(F) \rightarrow h_{n+t}(D^n \times F, S^{n-1} \times F;k) \rightarrow h_t(F) \rightarrow h_{n+t+1}(F) \rightarrow $ $

If this were an isomoprhism,this means that $ h_t(F) \cong h_{n+t+1}(F)$ for all $ n$ . This seems absurdly false.


I would hope some one may perhaps explain where I went wrong, and provide what the correct proposition may be. This question is motivated from my previous question.

In a Proof of Stake (PoS) mining scheme what prevents miners from producing many more blocks or inflating the currency?

In a traditional Proof of Work (PoW) scheme it’s assumed it takes some amount of time to compute the PoW function, such as SHA256x2 in Bitcoin and the difficulty increases as the network is capable of mining faster than the target 10 minutes.

In many Proof of Stake (PoS) schemes other metrics are used to determine if a miner was “selected” to have stake in the block, usually by looking at bits of TX inputs.

What keeps a PoS miner from having essentially infinite TX input hashes available on hand at any moment and mining blocks at a fast rate to inflate the currency / collect lots of subsidy rewards?

NP-hardness proof of selecting the best topological sequence of a DAG

Given a directed acyclic graph (DAG) with $ n$ vertexes $ V=\{v_1, v_2,…,v_n\}$ and a given permutation of those $ n$ vertexes $ P=[p_1, p_2,…, p_n]$ that $ \forall i, p_i\in V$ . Note that $ P$ could be in any order which includes the topological order. Now we want to find the best topological sequence $ L=[l_1, l_2,…, l_n]$ of the DAG that $ \forall i, l_i\in V$ .

The ”best” means the difference $ D$ between the two sequences $ P$ and $ L$ is minimal

$ $ D(P,L)=\sum_{i=1}^{n}f(p_i, l_i)$ $

$ $ f(x,y) = \begin{cases} 0 & x = y\ 1 & x \neq y \end{cases}$ $

For example, if $ P’$ itself is in topological order, then $ L’=P’$ is the answer since $ D(P’,L’)=0$ must be minimal.

I guess this problem is NP-hardness but couldn’t prove it.