Distinct solution to a linear congruence

Adams, Donald; Ponomarenko, Vadim

doi:10.2140/involve.2010.3.341

Download this article
	For screen
	For printing

Recent Issues

The Journal

About the journal

Ethics and policies

Peer-review process

Submission guidelines

ISSN 1944-4184 (online)

ISSN 1944-4176 (print)

Author index

To appear

Other MSP journals

Distinct solution to a linear congruence

Donald Adams and Vadim Ponomarenko

Vol. 3 (2010), No. 3, 341–344

DOI: 10.2140/involve.2010.3.341

Abstract

Given $n, k \in ℕ$ and $a_{1}, a_{2}, \dots, a_{k} \in ℤ_{n}$ , we give conditions for the equation $a_{1} x_{1} + a_{2} x_{2} + \dots + a_{k} x_{k} = 1$ in $ℤ_{n}$ to admit solutions with all the $x_{i}$ distinct.

A sufficient condition is that $k \leq ϕ (n)$ and $a_{i}$ be invertible in $ℤ_{n}$ for all $i$ .

If $n > 2$ is prime, the following conditions together are necessary and sufficient: $k \leq n$ , each $a_{i}$ is nonzero, and either $k < n$ or not all of the $a_{i}$ are equal.

Keywords

linear congruence, minimal zero-sum sequence, property B

Mathematical Subject Classification 2000

Primary: 11B50, 11D79

Milestones

Received: 7 July 2010

Revised: 29 September 2010

Accepted: 29 September 2010

Published: 16 October 2010

Proposed: Scott Chapman

Communicated by Scott Chapman

Authors

Donald Adams
Arizona State University Tempe, AZ 85287-1804 United States

Vadim Ponomarenko
San Diego State University Department of Mathematics and Statistics 5500 Campanile Dr. San Diego, CA 92182-7720 United States
http://www-rohan.sdsu.edu/~vadim/

Vol. 3, No. 3, 2010