Questions on congruences, linear diophantine equations, greatest common divisor, divisibility, etc.

learn more… | top users | synonyms (1)

2
votes
3answers
1k views

Given that a and b are integers, a ≡ 4 (mod 13), and b ≡ 9 (mod 13). Find c where c ≡ 9a (mod 13).

The Problem I had my first exposure to number theory today. Trying to work on some problems in hope that it will start to make more sense. Here is the problem (part a) I'm stuck on right now. My ...
2
votes
1answer
31 views

Question about classifying semidirect product

I have in some notes, this statement: Given $C_3\ltimes C_7$ we know that for $a\in C_3$ and $b\in C_7$, and some $k$: $$aba^{-1}=b^k$$ $$k^3\equiv 1(7)$$ The reason given is that $a^3=1$. ...
2
votes
2answers
64 views

remainder when $43$ divides $32002^{4200}$

what will be the remainder when $43$ divides $32002^{4200}$?? what I did is: $32002\equiv10 \pmod{43}$, how to proceed further?
2
votes
3answers
57 views

What is the solution of the following congruency

Well, I tried to solve this equation. I think, that I have to work with the Chinese remainder theorem. $$73x \equiv 1 \pmod{247} $$ $247=13×19$ so I may have to check the modulo $13$ and modulo $19$...
2
votes
1answer
40 views

Show that $a \equiv b$ (mod $n$) if and only if $r = s$.

Let $a, b \in \mathbb{Z}$ and let $n \in \mathbb{N}$. Write $a = qn + r$ and $b =q'n+s$ with $q,q' \in \mathbb{Z}$ and $r, s \in \{0,1,\ldots,n-1\}$ according to the divion algorithm. Show that $a \...
2
votes
1answer
101 views

Number of $0$ in the end of $11^n-1$

$n$ is integer, calculate number of $0$ in the end of $11^n-1$(i.e. largest integer $m$ such that $10^m|11^n-1$). The original question was $n=100$ and I could only choose $m$ from 1 to 5. I ...
2
votes
2answers
85 views

How to prove that $(p-1)^2$ $\mid$ $(p-1)!$ when $p$ is a prime number and $p>5$?

I say that $p-1$ $\mid$ $(p-1)!$ then I want to prove that $p-1$ $\mid$ $(p-2)!$. I started by saying that $p-1$ is an even number so $2\mid (p-1)$ and that means that $\frac{p-1}{2}$ is an integer. ...
2
votes
1answer
82 views

Find all positive integers $(x,y,z)$ such that $\frac{1}{x}+\frac{1}{y}+\frac{1}{z}$ is integer

As stated in title, I would like to find solution to this problem: Find all positive integers $(x,y,z)$ such that $\frac{1}{x}+\frac{1}{y}+\frac{1}{z}$ is also integer. I need idea how to solve ...
2
votes
1answer
40 views

Theory number problem

I need to prove that there are infinitely many natural numbers $n$ for which $2n^2+3$ and $n^2+n+1$ are relatively prime. This is not true for every $n$ (for example, $n=4$), I tried to check for odd ...
2
votes
2answers
93 views

Minimum sum of set whose average of subsets is positive integer

A finite set of positive integers $A$ is called meanly if for each of its nonempty subsets the arithmetic mean of its elements is also a positive integer. In other words, $A$ is meanly if $\frac{1}{k}(...
2
votes
1answer
54 views

Is it true that if $\gcd(a,b) = 1$ and $\gcd(a,c) = 1$ then $\gcd(ac,b) = 1$?

Is it true that if $\gcd(a,b) = 1$ and $\gcd(a,c) = 1$ then $\gcd(ac,b) = 1$? I know that $\gcd(a,b) = 1$ means that there exist integers $m$ and $n$ such that $am + bn = 1$ Same thing for $\gcd(a,...
2
votes
3answers
309 views

Non-linear diophantine equation

Let $k$ and $n$ be positive integers and $y(n-x)=(k+nx)$. What is the condition of $k$ and $n$ such that there exist positive integers $x, y$ as the solution of $y(n-x)=(k+nx)$?
2
votes
1answer
57 views

Simple polynomial factorization

If $f(x) = x^3 + (a-5)$, where $a$ is some integer. Find all the possibility of an integer $a$, such that $f(x)$ can be factorized. I did one example: If $ a = 4$, then $f(x) = x^3 -1$ and $x^3-1 = ...
2
votes
3answers
187 views

Sum of squares of two integers divisible by five [closed]

Supposing $x,y$ are natural numbers, what is the probability that the sum of their squares are divisible by 5? I am getting $1/3$ as squares can only end with $0,1,4,5,6,9$. So $36$ pairs are ...
2
votes
1answer
46 views

How to solve $n$ in $5^{n-1}\equiv 1 \pmod{n}$

$5^{n-1}\equiv 1 \pmod{n}$ I see that this holds true when $n$ is prime by Fermat's little theorem. However there could be few composite numbers, $n$ for which the congruence might hold true ? How to ...
2
votes
4answers
79 views

If $c\mid ab$ and $\gcd(c,a)=d$, then $c\mid db$

I came across this problem in my number theory text and am having a bit of trouble with it: Prove if $c\mid ab$ and $\gcd(c,a)=d$, then $c\mid db$. Here's what I have so far: If $c\mid ab$, then ...
2
votes
1answer
56 views

Assume that the order of $a$ in $ \pmod n$ is $h$ and the order of $b$ in $ \pmod n$ is $k$. Show that the order of $ab$ in $ \mod n$ divides $hk$

Assume that the order of $a$ in $ \pmod n$ is $h$ and the order of $b$ in $ \pmod n$ is $k$. Show that the order of $ab$ in $ \mod n$ divides $hk$ $ a^h \equiv 1 \pmod n $ $ b^k \equiv 1 \pmod n ...
2
votes
3answers
106 views

How do I prove that numbers not divisible by 3 can be represented as 3x+1 or 3x-1?

I saw that some proofs used the fact that numbers not divisible by $3$ can be represented as $3x+1$ or $3x-1$. But how do I prove that it is true?
2
votes
1answer
95 views

A question about how to express a fraction as ${1\over q_1}+{1\over q_2}+ \cdots+{1\over q_N}$

Let $x$ be a positive rational number, strictly between $0$ and $1$. Prove that there is a finite strictly increasing list of positive integers $2 \leq q_1<q_2<\cdots<q_N $ such that $$x={1\...
2
votes
3answers
125 views

Factorial as a sum. Insight appreciated

I recently posted an answer to a question about ways to express the factorial function as a sum. I posted the following formula, which I discovered several years ago and I haven't seen anywhere else: ...
2
votes
2answers
247 views

Solutions of Diophantine equation

Does there exists any other solutions of the following Diophantine equation $$zx^2 +xy^2 +yz^2 =xyzt .$$ I found that $$(x,y,z,t) =(s,s,s,3) ,(x,y,z,t)=(s,2s,4s ,5)$$ where $s\in\mathbb{N}$ are ...
2
votes
2answers
92 views

general form in congruence

Could we generalize this example of congruence issue for $x,n \in \mathbb{Z}_*$? $$ 1+x+\cdots + x^{n-1}\equiv n \pmod {x-1} $$
2
votes
2answers
111 views

congruence issue

I need to understand why this : $$(1+4+\ldots+4^{n−1})\equiv n \pmod3$$ Is that because \begin{align} 1&\equiv -2 \pmod3\\ 4&\equiv 1 \pmod3\\ 4^{2}&\equiv1 \pmod3\\ \ldots&\equiv\...
2
votes
4answers
259 views

The final digit of fourth powers

I am working on "Elementary Number Theory" By Underwood Dudley and this is problem 13 in Section 4. The question is "What can the last digit of a fourth power be?" I got the correct answer but I'm ...
2
votes
1answer
85 views

If $\gcd(r,s)=1$, which numbers can be written as a linear combination $as+br$ with $a,b$ nonnegative?

I know if $gcd(r,s)=1$ then $1=as+bs$ for some intgers $a,b$. Here's what I want to know: which numbers can be written as $as+br$, if I am restricted to $a,b \in \mathbb{N}$? To be more specific, I ...
2
votes
2answers
91 views

Solution of an equation involving even integers

If $x$ is any positive even integer $> 1$. I compute: $$ c = x + x! $$ Now assume instead $c$ (even integer) is given, and I want to get back the value $x$. Is it possible to find a simple ...
2
votes
2answers
47 views

Finding a two-digit number.

The sum of the digits of a two-digit number is $9$. When we intrchange the digits,it is found that the resulting new number is greater than the original number by $27$. What is two digit number?
2
votes
1answer
159 views

Given $n$, find smallest number $m$ such that $m!$ ends with $n$ zeros

I got this question as a programming exercise. I first thought it was rather trivial, and that $m = 5n$ because the number of trailing zeroes are given by the number of factors of 5 in $m!$ (and ...
2
votes
1answer
89 views

How to efficiently find the largest perfect square dividing a given large integer?

Given a number $n$. I need to find the largest $q$ such that $q^2$ divides $n$. I need the fastest method to find $q$. $q$ can be any number prime or composite. At present I am factorizing the number ...
2
votes
5answers
34 views

Proving that $nb \text{ (mod m)}$ reaches all values $\{0 \dots (m-1)\}$ if $n$ and $m$ are relatively prime

I am trying to prove the frobenius coin problem which requires me to prove the following lemma: If $n$ and $m$ are relatively prime and $b$ is any integer, then the set of all possible values of $$nb ...
2
votes
2answers
92 views

An exercise in number theory: euclidean domain

I have an exercise for you about euclidean domain. Which primes $p<30$ in $\mathbb{Z}$ is a prime in $ \mathbb{Z} \left[ \frac{1+\sqrt{-7}}{2} \right] $ ? Thank you very much for the support, I ...
2
votes
1answer
162 views

Solutions to a diophantine equation

I tried to find integer solutions to the following diophantine equation $$x^3 - 3y^3 + 5z^3 - 3xy^2 + 3x^2y + 9xz^2 + 7x^2z + 3yz^2 - 3y^2z + xyz = 0$$ but was unable to do so. I suspect that there ...
2
votes
2answers
46 views

Dividing by x on two sides of an equation is not always the same equation??

$y = p*x$ $\frac{y}{x} = \frac{p*x}{x}$ These equations are 'equal' via common math principles. If $x = 0$, then in the first equation $y = 0$. In the second equation, its not defined (since you ...
2
votes
3answers
56 views

Chinese Remainder Theorem problem error

I am trying to find all integers that give remainders 1,2,3 when divided by 3,4,5 respectively. So I start defining $$a_1=1, a_2=2, a_3=3,$$$$ m_1=3, m_2=4, m_3=5,$$$$ m_1m_2=12, m_1m_3=15, m_2m_3=...
2
votes
3answers
304 views

Divisibility of consecutive numbers by 6

Prove that the product of three consecutive positive integers is divisible by 6 by expressing the positive integer n as n=8*q+r I expressed the problem as n(n+1)(n+2) where n is a positive integer I ...
2
votes
2answers
67 views

Correct reasoning when proving the multiplication property in modular arithmetic?

I am trying to understand why this rule works: \begin{align*} a \equiv b \pmod c \quad k \equiv j \pmod c \qquad &\implies \qquad ka\equiv jb \pmod c \end{align*} I saw that the proof is $ka-...
2
votes
5answers
87 views

Proof regarding divisibility

if $n\in\mathbb{Z}$, then $4$ does not divide $(n^2 - 3)$ I'm not sure how to approach this question, I know how to do questions that involve proving that it does divide but I'm unsure of how to do ...
2
votes
1answer
58 views

$[n,n+1]=\text{ ??????}$

I know the answer is $n(n+1)$, but I'm having trouble formulating an argument. I know by the definition, if I let $h=[n,n+1]$ $$h=nk_1, h=(n+1)k_2$$ $$nk_1=(n+1)k_2$$ $$\frac{n}{n+1}=\frac{k_2}{k_1}$$...
2
votes
5answers
379 views

Number theory problem book

Can anyone suggest me some good book that has problems on classical elementary number theory with solutions?
2
votes
1answer
87 views

How to calculate “gcd product” $\operatorname{gcdp}(n,m)=\gcd(n,1)\gcd(n,2)\cdots\gcd(n,m)$

Given two numbers $m$ and $n$ how can we calculate the gcd product of any two numbers i.e, $\operatorname{gcd p}(n,m)=\gcd(n,1)\gcd(n,2)\cdots\gcd(n,m)$ where gcd is the greatest common divisor? Can ...
2
votes
1answer
655 views

Show that the converse of Fermats Little Theorem is false using a counter example.

Show that the converse of Fermat's little theorem is false using a counter example. Show that $$a^{561} \equiv a \pmod p$$ and hence that the converse of Fermat's little theorem is false???
2
votes
2answers
238 views

Second Course in Number Theory - Self Study

I just finished a first course in number theory using Dudley's Elementary Number Theory. This was by far my favorite math course and I want to learn more number theory this summer. As far as ...
2
votes
2answers
1k views

Find the remainder when $2(26!)$ is divided by $29$.

Find the remainder when $2(26!)$ is divided by $29$. So I know I'm going to use Wilson's theorem and then I would have $28!=-1(\mod29\:)$ but what is the next step? Step by Step explanation please!
2
votes
1answer
73 views

Find all integers n such that n−2014 and n+ 2014 are both triangular numbers.

I came across this problem when searching for triangular numbers questions. I know that I need to use the equation, $$\frac {n(n+1)}{2} $$ but I don't know how to apply it to this problem.
2
votes
2answers
195 views

Using Chinese Remainder Theorem to Prove Existence of An Integer

The question goes like this: use the CRT to prove that if an integer $n>1$ is not a power of a prime, then there exists an integer $x$ such that $n|(x^{2}-x)$ but $n$ does not divide $x$ nor $x-1$. ...
2
votes
2answers
245 views

Let q be an odd integer such that p = 4q+1 is prime.

Let $q$ be an odd integer such that $p = 4q+1$ is prime. a. Show that $(2|p) = -1$ b. Prove that $p | (4^q+1)$ So far I see that: $(2|p) = (-1)^{ (\frac{(p^2-1)}{(8)} )}$. Not sure if this helps ...
2
votes
1answer
73 views

Is a Mersenne prime always of the form $4n + 3$?

Is a Mersenne prime always of the form $4n + 3$? Examples: $M_3 = 7 = 4 \times 1 + 3$ $M_5 = 31 = 4 \times 7 + 3$ $M_7 = 127 = 4 \times 31 + 3$ $M_{13} = 8191 = 4 \times 2047 + 3$
2
votes
2answers
67 views

Describe all integers a for which the following system of congruences (with one unknown x) has integer solutions:

$$x\equiv a \pmod {100}$$ $$x\equiv a^2 \pmod {35}$$ $$x\equiv 3a-2 \pmod {49}$$ I'm trying to solve this system of congruences, but I'm only familiar with a method for solving when the mods are ...
2
votes
1answer
82 views

Problem on Number of Quadratic Residues

We have two primes $p,q$ and an integer $a$ such that $$\gcd(a,pq)=1$$ How to prove that for the following congruence $$x^2 \equiv a \mod pq$$ either there will be $4$ solutions or $zero$ solutions. ...
2
votes
1answer
54 views

Don't know where to start…

Should I count it by hand, or there is a general mechanism? Let N be the largest positive integer with the following property: reading from left to right, each pair of consecutive pair of consecutive ...