Search Results

You are looking at 1 - 5 of 5 items for :

  • "greatest common divisor" x
  • Mathematics and Statistics x
  • All content x
Clear All

A graphH divides a graphG, writtenH|G, ifG isH-decomposable. A graphG without isolated vertices is a greatest common divisor of two graphsG 1 andG 2 ifG is a graph of maximum size for whichG|G 1 andG|G 2, while a graphH without isolated vertices is a least common multiple ofG 1 andG 2 ifH is a graph of minimum size for whichG 1|H andG 2|H. It is shown that every two nonempty graphs have a greatest common divisor and least common multiple. It is also shown that the ratio of the product of the sizes of a greatest common divisor and least common multiple ofG 1 andG 2 to the product of their sizes can be arbitrarily large or arbitrarily small. Sizes of least common multiples of various pairsG 1,G 2 of graphs are determined, including when one ofG 1 andG 2 is a cycle of even length and the other is a star.

Restricted access

Abstract  

We prove that for any positive real number

\documentclass{aastex} \usepackage{amsbsy} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{bm} \usepackage{mathrsfs} \usepackage{pifont} \usepackage{stmaryrd} \usepackage{textcomp} \usepackage{upgreek} \usepackage{portland,xspace} \usepackage{amsmath,amsxtra} \pagestyle{empty} \DeclareMathSizes{10}{9}{7}{6} \begin{document} $$c$$ \end{document}
which is not an integer, the density of the integers
\documentclass{aastex} \usepackage{amsbsy} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{bm} \usepackage{mathrsfs} \usepackage{pifont} \usepackage{stmaryrd} \usepackage{textcomp} \usepackage{upgreek} \usepackage{portland,xspace} \usepackage{amsmath,amsxtra} \pagestyle{empty} \DeclareMathSizes{10}{9}{7}{6} \begin{document} $$n$$ \end{document}
which are coprime to
\documentclass{aastex} \usepackage{amsbsy} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{bm} \usepackage{mathrsfs} \usepackage{pifont} \usepackage{stmaryrd} \usepackage{textcomp} \usepackage{upgreek} \usepackage{portland,xspace} \usepackage{amsmath,amsxtra} \pagestyle{empty} \DeclareMathSizes{10}{9}{7}{6} \begin{document} $$n^c {\text{ is }}6/\pi ^2$$ \end{document}
, a result conjectured by Moser, Lambek and Erd Hs.

Restricted access

Abstract  

For any positive integer n let Fn be the n-th Fibonacci number. Given positive integers a and b, we study the size of the greatest common divisor of Fn + a and Fm + b for varying positive integers m and n.

Restricted access

Abstract  

We study those functions that can be written as a finite sum of periodic integer valued functions. On ℤ we give three different characterizations of these functions. For this we prove that the existence of a real valued periodic decomposition of a ℤ → ℤ function implies the existence of an integer valued periodic decomposition with the same periods. This result depends on the representation of the greatest common divisor of certain polynomials with integer coefficients as a linear combination of the given polynomials where the coefficients also belong to ℤ[x]. We give an example of an ℤ → {0, 1} function that has a bounded real valued periodic decomposition but does not have a bounded integer valued periodic decomposition with the same periods. It follows that the class of bounded ℤ → ℤ functions has the decomposition property as opposed to the class of bounded ℝ → ℤ functions. If the periods are pairwise commensurable or not prescribed, then we get more general results.

Restricted access