On the greatest common divisor of shifted sets

Randell Heyman; Igor E. Shparlinski

doi:10.1016/j.jnt.2015.02.012

On the greatest common divisor of shifted sets

Randell Heyman^*, Igor E. Shparlinski

^*Corresponding author for this work

Research output: Contribution to journal › Article › peer-review

1 Citation (Scopus)

Abstract

Given a set of n positive integers {a₁, ..., a_n} and an integer parameter H we study the greatest common divisor of small additive shifts of its elements by integers h_i with |h_i| ≤ H, i = 1, ..., n. In particular, we show that for any choice of a₁, ..., a_n there are shifts of this type for which the greatest common divisor of a₁ + h₁, ..., a_n+h_n is much larger than H.

Original language	English
Pages (from-to)	63-73
Number of pages	11
Journal	Journal of Number Theory
Volume	154
DOIs	https://doi.org/10.1016/j.jnt.2015.02.012
Publication status	Published - 1 Sept 2015
Externally published	Yes

Keywords

Approximate GCD
GCD

Access to Document

10.1016/j.jnt.2015.02.012

Cite this

@article{4047427fcda84bac97914e54bb4cc69b,

title = "On the greatest common divisor of shifted sets",

abstract = "Given a set of n positive integers {a1, ..., an} and an integer parameter H we study the greatest common divisor of small additive shifts of its elements by integers hi with |hi| ≤ H, i = 1, ..., n. In particular, we show that for any choice of a1, ..., an there are shifts of this type for which the greatest common divisor of a1 + h1, ..., an+hn is much larger than H.",

keywords = "Approximate GCD, GCD",

author = "Randell Heyman and Shparlinski, {Igor E.}",

year = "2015",

month = sep,

day = "1",

doi = "10.1016/j.jnt.2015.02.012",

language = "English",

volume = "154",

pages = "63--73",

journal = "Journal of Number Theory",

issn = "0022-314X",

publisher = "Academic Press Inc.",

}

TY - JOUR

T1 - On the greatest common divisor of shifted sets

AU - Heyman, Randell

AU - Shparlinski, Igor E.

PY - 2015/9/1

Y1 - 2015/9/1

N2 - Given a set of n positive integers {a1, ..., an} and an integer parameter H we study the greatest common divisor of small additive shifts of its elements by integers hi with |hi| ≤ H, i = 1, ..., n. In particular, we show that for any choice of a1, ..., an there are shifts of this type for which the greatest common divisor of a1 + h1, ..., an+hn is much larger than H.

AB - Given a set of n positive integers {a1, ..., an} and an integer parameter H we study the greatest common divisor of small additive shifts of its elements by integers hi with |hi| ≤ H, i = 1, ..., n. In particular, we show that for any choice of a1, ..., an there are shifts of this type for which the greatest common divisor of a1 + h1, ..., an+hn is much larger than H.

KW - Approximate GCD

KW - GCD

UR - http://www.scopus.com/inward/record.url?scp=84926432121&partnerID=8YFLogxK

UR - http://purl.org/au-research/grants/arc/DP130100237

U2 - 10.1016/j.jnt.2015.02.012

DO - 10.1016/j.jnt.2015.02.012

M3 - Article

AN - SCOPUS:84926432121

SN - 0022-314X

VL - 154

SP - 63

EP - 73

JO - Journal of Number Theory

JF - Journal of Number Theory

ER -

On the greatest common divisor of shifted sets

Abstract

Keywords

Access to Document

Other files and links

Fingerprint

Cite this