Tour:Interdisciplinary problems four (beginners)
This page is a Interdisciplinary problems page, part of the Groupprops guided tour for beginners (Jump to beginning of tour)
PREVIOUS: Hard nuts four (beginners)| UP: Introduction four | NEXT: Confidence aggregator four (beginners)
PREVIOUS SECTION Interdisciplinary problems: Interdisciplinary problems three|NEXT SECTION Interdisciplinary problems: Interdisciplinary problems five
General instructions for the tour | Pedagogical notes for the tour | Pedagogical notes for this part
The problems here relate ideas in group theory to ideas in other subjects. Learners who already have some experience with the other subjects may try these problems to cement their understanding of what has been learned in parts one and two of the tour. Moreover, some of these problems build on themes introduced in Tour:Interdisciplinary problems two (beginners) and Tour:Interdisciplinary problems three (beginners), so a review of those problems may be helpful.
Contents
Subsets of cyclic groups upto the square root size
- NEEDS LOT OF THOUGHT: Prove that there exists a quadratic nonresidue mod
represented by a positive integer less than
. (Hint: Look at the smallest quadratic nonresidue.) For full proof, refer: Number:Smallest quadratic nonresidue is less than square root plus one
- Extend the previous result to prove that there exists a quadratic nonresidue mod
represented by a prime integer less than
.
- The
Fermat number,
, is defined as
. A Fermat number that is prime is termed a Fermat prime. Prove that any quadratic nonresidue mod a Fermat prime, is a primitive root for it. Using this, prove that for a Fermat prime
, there exists a primitive root mod
between 1 and
.
- Prove that the multiplicative group mod
is generated by the congruence classes of all primes
less than
(this is a generalization of the ideas of problems (1) and (2)). For full proof, refer: Number:Multiplicative group of a prime field is generated by all primes less than square root plus one
Quadratic residues and primality testing
Strong pseudoprimes and Rabin-Miller primality testing
Further information: Number:Strong pseudoprime, Number:Rabin-Miller primality test
- Strong pseudoprime: Consider the following property for numbers
and
if
, and further, the following holds. if
where
is odd, then in the sequence
, either all the entries are
mod
, or the last entry which is not
mod
, is -1 mod
. Prove that if
is prime, the property holds for all
relatively prime to
. A composite number
is termed a strong pseudoprime to base
if it satisfies the above property with
.
- Prove that every strong pseudoprime to base
is also a Fermat pseudoprime to base
.
- For a positive integer
, define
to be the set of
such that
is a strong pseudoprime to base
. Prove that
is a subset of the group
of all invertible elements mod
, under multiplication. Also, prove that
contains the identity element and is closed under inverses.
- NEEDS SOME THOUGHT: Prove that if
is composite, then
is a proper subset of the group
.
- NEEDS LOT OF THOUGHT: Explore: Can you bound the ratio
by a number strictly less than 1?
Quadratic residues
Further information: Number:Euler pseudoprime
- Euler pseudoprime: Prove that if
is an odd prime and
is relatively prime to
, then
. We say that a composite number
is an Euler pseudoprime to base
if
.
- Prove that a strong pseudoprime is an Euler pseudoprime.
Discrete logarithm
The multiplicative group of integers mod is a cyclic group of order
. A discrete logarithm on this group is an isomorphism from this group to the group of integers mod
.
- Prove that there is a correspondence between primitive roots (generators of the multiplicative cyclic group) mod
and discrete logarithms on the multiplicative group mod
. Hence, prove that there are
discrete logarithms.
- Assuming the availability of a discrete logarithm table mod
, explain how the problem of solving
(where
is the unknown) reduces to solving a linear equation mod
.
Combinatorics
Sidon subsets
A subset of an Abelian group
is termed a Sidon subset if there do not exist four distinct
such that
in
.
- Suppose
are four nonnegative integers. Prove that if
and
, then
.
- Let
be the cyclic group of order
, for some prime
. For any integer
, let
denote the remainder on dividing
by
. Consider the subset
of
given by
. Prove that
is a Sidon subset of
.
- Bertrand's postulate states that for any positive integer
, there exists a prime
such that
. Using Bertrand's postulate, prove that the cyclic group of order
, for any
, has a Sidon subset of size at least
.
Fibonacci sequences
The Fibonacci numbers are defined as follows: ,
, and
for
. There is a formula for
, called Binet's formula:
where . The formula is easily proved by induction.
- Let
be an odd positive integer. Prove that if there exists an integer
such that
, then there exists a positive integer
such that
, and:
Explore: Can you use this to determine the period of the Fibonacci sequence mod ?
The combinatorics of algebraic structures
Up to isomorphism
- Suppose
is a finite set of cardinality
. Consider the binary operations
, upto isomorphism. Two binary operations
are isomorphism if there is a permutation
such that
. Prove that the number of binary operations up to equivalence is between
and
.
- Consider all the possible binary operations on a set of size two. Classify all these binary operations up to isomorphism.
Up to isotopy
Let and
be magmas. An isotopy of magmas from
to
is a triple of bijective maps
from
to
, such that, for all
:
.
- Classify all the magmas of size two up to isotopy.
- Prove that if two groups are isotopic as magmas, they are isomorphic as groups.
- Prove that any magma isotopic to a quasigroup is a quasigroup.
Universal algebra
Opposite group
Recall the notion of opposite from the interdisciplinary problems of part three.
- Prove that the inverse map defines an isomorphism between any group and its opposite group. In other words,
is an isomorphism from a group to its opposite group.
- Justify the natural bijection between left and right cosets of a subgroup in light of this isomorphism.
This page is a Interdisciplinary problems page, part of the Groupprops guided tour for beginners (Jump to beginning of tour)
PREVIOUS: Hard nuts four (beginners)| UP: Introduction four | NEXT: Confidence aggregator four (beginners)
PREVIOUS SECTION Interdisciplinary problems: Interdisciplinary problems three|NEXT SECTION Interdisciplinary problems: Interdisciplinary problems five
General instructions for the tour | Pedagogical notes for the tour | Pedagogical notes for this part