E 17

Art of Problem Solving

AoPS Online

PEN Math problems from the collection "Problems in Elementary Number Theory"

Math problems from the collection "Problems in Elementary Number Theory"

3 M G

BBookmark VNew Topic kLocked

PEN Math problems from the collection "Problems in Elementary Number Theory"

Math problems from the collection "Problems in Elementary Number Theory"

3 M G

BBookmark VNew Topic kLocked

No tags match your search

M

E 17

G H J

Reveal topic tags

L

G H BBookmark kLocked kLocked NReply

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

3615 posts

Peter

#1 h May 25, 2007, 12:24 AM • 1 Y

Y by Adventure10

Let $a$ , $b$ , and $n$ be positive integers with $\gcd (a, b)=1$ . Without using Dirichlet's theorem, show that there are infinitely many $k \in \mathbb{N}$ such that $\gcd(ak+b, n)=1$ .

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

133 posts

#2 h Aug 13, 2007, 9:34 PM • 2 Y

Y by Adventure10, Mango247

Let $\mathbb{P}= \{p \in \mathbb{N}: p \mbox{ is prime}\}$ and $\mathcal{Q}= \{p \in \mathbb{P}: p \mid n\;\wedge\;p \nmid b\}$ . Then letting $k = q \cdot \prod_{p \in \mathcal{Q}}p$ yields $\gcd(ak+b, n) = 1$ , for each $q \in \mathbb{P}$ such that $q > n$ .

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

1313 posts

TTsphn

#3 h Oct 26, 2007, 7:34 AM • 2 Y

Y by Adventure10, Mango247

Consequence
There exist infinite prime number.

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

3615 posts

Peter

#4 h Oct 26, 2007, 12:51 PM • 2 Y

Y by Adventure10, Mango247

s.tringali wrote:

Let $\mathbb{P} = \{p \in \mathbb{N}: p \mbox{ is prime}\}$ and $\mathcal{Q} = \{p \in \mathbb{P}: p \mid n\;\wedge\;p \nmid b\}$ . Then letting $k = q \cdot \prod_{p \in \mathcal{Q}}p$ yields $\gcd(ak + b, n) = 1$ , for each $q \in \mathbb{P}$ such that $q > n$ .

I don't understand. What if $\mathcal Q$ is empty, for example if $n|b$ ? What if $\mathcal Q$ is infinite? Then $\prod_{p \in \mathcal{Q}}p$ is not a number.

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

1313 posts

TTsphn

#5 h Oct 26, 2007, 1:10 PM • 3 Y

Y by Adventure10, Mango247, and 1 other user

I am also.
Here is my solution:
Enough to prove exist because if $\gcd(ak + b,n) = 1$ then $\gcd(a(k + nt) + b,m) = 1$
Now we prove this :
$n = \prod_{i = 1}^rp_i^{a_i}$ where $a_i > 0$
Now place each of them to one of set.
$A = \{p\in P: p|\gcd(b,n)\}$
$B = \{p\in P: p|n,\gcd(p,b) = 1\}$
Because $\gcd(a,b) = 1$ so $p\not|a,\forall p\in A$
Now we consider the system of congruent:
$k\equiv 1 (\mod\prod_{p\in A}p)$
$k\equiv 0 (\mod \prod _{p\in B})$
This equation has solution (Chinese remainder theorem).
Easy to check that $\gcd(ak + b,n) = 1$

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

14 posts

#6 h Apr 30, 2008, 12:25 PM • 3 Y

Y by AmazingMonkey, Adventure10, Mango247

It seems like this should have a simple arithmetic solution, since it can be rephrased as:

Let a, b, n, x and y be integers with $ax+by=1$ and $n\ne 0$ . Show that there exists integers z, k and w such that $z(ak+b)+wn=1$ .

The closest I could come does use the following lemma.

Lemma: For every pair of positive integers $n, b$ , there exists a representation $n=n_1n_2$ where $n_2$ is coprime to $b$ and $n_1$ is a factor of a power of $b$ .

Proof: Let $t_0=n$ , and define sequences $t_i, u_i$ by $u_i=\gcd(t_i,b)$ , $t_{i+1}=\frac{t_i}{u_i}$ . Since $u_i\ge 1$ , $t_{i+1}\le t_i$ and the positive integer sequence eventually becomes constant. Suppose $t_k=t_{k+1}$ . Then set $n_2=t_k$ and $n_1=u_1u_2\ldots u_{k-1}$ . Clearly $n=n_2$ , $t_k$ is coprime to $b$ , and since each $u_i$ is a factor of $b$ , $n_1$ is a factor of $b^{k-1}$ .
QED

It is not hard to see that this representation is unique, but we won't use that.

Given our n, a, b from the problem, we know that $\gcd(a,b)=1$ , which means that $\gcd(b,a+b)=1$ . From the above lemma, we can write $n=n_1n_2$ where $n_2$ is coprime to $b$ and $n_1$ is a factor of a power of $b$ . Since $n_1$ is a factor of a power of $b$ , it is coprime to all things coprime to $b$ , in particular to $n_2$ and to $a+b$ .

Thus we have the existence of integers $x_i, y_i$ such that $x_1n_1+y_1n_2=1$ , $x_2n_1+y_2(a+b)=1$ and $x_3n_2+y_3b=1$ .

Then: $y_3(b+y_1n_2a)=y_3b+y_3y_1n_2a=1-x_3n_2+y_3y_1n_2a=1+(y_3y_1a-x_3)n_2$ , so $b+y_1n_2a$ is coprime to $n_2$ .

Similarly, $y_2(b+y_1n_2a)=y_2(b+(1-x_1n_1)a)=y_2(b+a)-y_2x_1n_1a=1-x_2n_1-y_2x_1n_1a=1-(x_2+y_2x_1a)n_1$ ,
so $b+y_1n_2a$ is coprime to $n_1$ .

Thus $b+y_1n_2a$ is coprime to $n_1n_2=n$ .

Luke
See my puzzle blog at http://bozzball.blogspot.com/[/b]

Z K Y

N Quick Reply

G

H

=

© 2025 AoPS Incorporated

a