• :00Days
• :00Hours
• :00Mins
• 00Seconds
A new era for learning is coming soon Suggested languages for you:

Europe

Answers without the blur. Sign up and see all textbooks for free! Q15E

Expert-verified Found in: Page 272 ### Discrete Mathematics and its Applications

Book edition 7th
Author(s) Kenneth H. Rosen
Pages 808 pages
ISBN 9780073383095 # Which positive integers less than 30 are relatively prime to 30?

1, 7, 11, 13, 17, 19, 23, 29

See the step by step solution

## Step 1

The integers $a$ and $b$ are relatively prime, if their greatest common divisor is 1.

Let us determine the greatest common divisor of 30 and every integer less than 30.

$\begin{array}{c}\mathrm{gcd}\left(30,1\right)=1\\ \mathrm{gcd}\left(30,2\right)=2\\ \mathrm{gcd}\left(30,3\right)=3\\ \mathrm{gcd}\left(30,4\right)=4\\ \mathrm{gcd}\left(30,5\right)=5\\ \mathrm{gcd}\left(30,6\right)=6\\ \mathrm{gcd}\left(30,7\right)=7\\ \mathrm{gcd}\left(30,8\right)=8\\ \mathrm{gcd}\left(30,9\right)=9\\ \mathrm{gcd}\left(30,10\right)=10\\ \mathrm{gcd}\left(30,11\right)=1\\ \mathrm{gcd}\left(30,12\right)=6\\ \mathrm{gcd}\left(30,13\right)=1\\ \mathrm{gcd}\left(30,14\right)=2\\ \mathrm{gcd}\left(30,15\right)=5\\ \mathrm{gcd}\left(30,16\right)=2\\ \mathrm{gcd}\left(30,17\right)=1\\ \mathrm{gcd}\left(30,18\right)=6\\ \mathrm{gcd}\left(30,19\right)=1\\ \mathrm{gcd}\left(30,20\right)=10\end{array}$

## Step 2

$\begin{array}{r}\mathrm{gcd}\left(30,21\right)=3\\ \mathrm{gcd}\left(30,22\right)=2\\ \mathrm{gcd}\left(30,23\right)=1\\ \mathrm{gcd}\left(30,24\right)=6\\ \mathrm{gcd}\left(30,25\right)=5\\ \mathrm{gcd}\left(30,26\right)=2\\ \mathrm{gcd}\left(30,27\right)=3\\ \mathrm{gcd}\left(30,28\right)=2\\ \mathrm{gcd}\left(30,29\right)=1\end{array}$

The positive integers less than 30 that are relatively prime to 30 are then all integers $a$ for which $\mathrm{gcd}=\left(30,1\right)=1$.

$a=1,7,11,13,17,19,23,29$ ### Want to see more solutions like these? 