If a prime $p$ is divided by 30, remainder is either prime or 1 Show that if a prime number $p$ is divided by 30, then the remainder is either a prime or 1.
I did the sum sum but cannot complete it.
I took $p=6k+1$ and $p=6k-1$ form.
now for any $k=5m$ we get $6k=30m$ form so we can say that the remainder comes 1 but then I can't give proper proof of the rest.
 A: Make a list of all the integers $r$ such that $0\le r\le 29$ and $r$ is not $1$ or a prime. 
These numbers are 
$$0,4,6,8,9,10,12,14,15,16,18,20,21,22,24,25,26,27,28.$$
For each number $r$ in this list, give an argument that if $n$ has remainder $r$ on division by $30$, then $n$ cannot be prime. 
You will be able to deal with the numbers in bunches. For example, if $r$ is one of the even numbers in the list, and $n$ has remainder $r$, then $n$ cannot be prime since it is greater than $2$ and divisible by $2$.  
Remark: The result does not generalize in any nice way. It turns out that $30$ is the largest number $m$ such that any number between $2$ and $m$ which is relatively prime to $m$ is prime. 
A: A very elementary solution :Any number is of the form $30k+c$ where $k\in N$ and $c\in \{0,1,2,\dots,29\}$
Now you can easily see that as the number is prime so $c\notin \{0,2,4,\dots,28\}$ ,$c\notin \{0,3,6,\dots 27\}$ , $c\notin \{0,5,10,\dots 25\}$,$c\notin \{0,3,6,\dots 27\}$ So the only number that remains are the primes and $1$.
In your approach: Take $k=5m+c$ for $m\in N$ and $c\in \{0,1,2,3,4\}$ and check explicitly the cases .You will get the solution.
A: Assume by contradiction that the remainder is not $1$ or prime.  The prime factors of $30$ are $2$, $3$, and $5$, and since $p$ is prime, the remainder must contain the product of two primes both greater than $5$, but then the remainder is greater than $30$, a contradiction.
A: You can contradict the statement by taking a number in the form of $30q+n$ where $n$ is any composite number between $1$ and $30$.
You will find in the case of even numbers $2$ is a common factor, and in the case of odd numbers $3$ and/or $5$ are factors.
Therefore all primes are of form $30q+n$ where $n$ is either prime or $1$.
A: If $p$ is a prime not exceeding $29$ the remainder $R$ is $p$ itself.
If $p$ is a prime greater than $30$ the remainder  $R$ is from $0$ to $29,$ and we have :
...$R\ne 0, $ else  $30|p ,$ implying  $p$ is not prime.
...$2\not |R, $ else $2|p>2, $ implying $p$ is not prime.
...$3\not| R, $ else $3|p>3, $ implying $p$ is not prime. 
...$5\not |R, $ else $5|p>5$, implying $p$ is not prime.
So for prime $p>30,$ the remainder $R$ is positive and not divisible by any prime $q\leq \sqrt R,$ so $R=1$ or $ R$ is prime. 
