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

learn more… | top users | synonyms (1)

8
votes
1answer
520 views

Prove that if $\sigma(n)=2n+1$ then $n$ is an odd perfect square.

Prove that if $\sigma(n)=2n+1$ then $n$ is an odd perfect square. (Here, $\sigma(n)$ is the sum of the positive divisors of $n$ including 1 and $n$ itself.) As I know, this $n$ is a quasiperfect ...
14
votes
5answers
445 views

Alternate proof that for every natural number $n,\ \left\lfloor\left(\frac{7+\sqrt{37}}{2}\right)^n\right\rfloor$ is divisible by $3$

Original Problem: Prove that for every natural number $n$,$$\left\lfloor\left(\frac{7+\sqrt{37}}{2}\right)^n\right\rfloor$$ is divisible by $3$. I found the problem in the book Winning ...
7
votes
2answers
176 views

$n\mid \phi(a^{n}-1)$ for any $a>n$?

I saw the proof which goes as follows: $a^{n} \equiv 1 \pmod{a^{n}-1} $, and $n$ is the smallest power of a such that this is true. We also know that by Euler's Identity $a^{\phi(a^{n}-1)}\equiv ...
3
votes
2answers
108 views

Same number of solutions to $ax^m+by^n\equiv c\pmod{p}$ and $ax^{m'}+by^{n'}\equiv c\pmod{p}$.

I'm having trouble with the last problem of Chapter 4 in Ireland and Rosen's Number Theory. Show that $ax^m+by^n\equiv c\pmod{p}$ has the same number of solutions as $ax^{m'}+by^{n'}\equiv ...
8
votes
1answer
565 views

Why does $p^2+8$ prime imply $p^3+4$ prime

How do I prove that $p^2+8$ prime implies that $p^3+4$ is prime? What is the general pattern of thought for these problems?
1
vote
4answers
144 views

Proving that $\alpha^{n-2}\leq F_n\leq \alpha^{n-1}$ for all $n\geq 1$, where $\alpha$ is the golden ratio

I got stuck on this exercise. It is Theorem 1.15 on page 14 of Robbins' Beginning Number Theory, 2nd edition. Theorem 1.15. $\alpha^{n-2}\leq F_n\leq \alpha^{n-1}$ for all $n\geq 1$. Proof: ...
2
votes
2answers
83 views

If $p\equiv 1\pmod{8}$, then $-1$ is fourth power?

I know that $-1$ is a square modulo $p$ iff $p\equiv 1\pmod{4}$. Curious about this, I'm trying to show that $-1$ is a fourth power if and only if $p\equiv 1\pmod{8}$, for $p$ odd. I know that if ...
7
votes
2answers
248 views

$3x^2 ≡ 9 \pmod{13}$

What is $3x^2 ≡ 9 \pmod{13}$? By simplifying the expression as $x^2 ≡ 3 \pmod{13}$ and applying brute force I can show that the answers are 4 and 9, but how to approach this in a more efficient way? ...
0
votes
2answers
75 views

Transform a positive integer to find its next greatest factor

Suppose I am trying to find factors of a particular positive integer num. Suppose I also have a function findGreatestFactor(num) ...
5
votes
3answers
595 views

What is $1^k+2^k+\cdots+ (p-1)^k$ modulo $p$? (From Ireland and Rosen).

I've been working through a bit of Ireland and Rosen's Number Theory for fun. Problem 4.11 of Ireland and Rosen asks Prove that $1^k+2^k+\cdots+(p-1)^k\equiv 0\pmod{p}$ if $p-1\nmid k$, and ...
7
votes
5answers
263 views

how many number like $119$

How many 3-digits number has this property like $119$: $119$ divided by $2$ the remainder is $1$ 119 divided by $3$ the remainderis $2 $ $119$ divided by $4$ the remainder is $3$ $119$ divided by ...
10
votes
5answers
2k views

Prove that odd perfect square is congruent to $1$ modulo $8$

How can we prove that every odd perfect square is congruent to $1$ modulo $8$?
1
vote
1answer
430 views

For which primes $p$ does $x^2-31y^2=-p$ have solutions?

This is an exam question from Number theory (especially of quadratic field extensions): For which prime number $p$ can we solve the Diophantine equation $x^2-31y^2=-p$. Find also a solution for ...
9
votes
1answer
291 views

Möbius function from random number sequence

Consider some arbitrary number sequence like the decimal expansion of $\pi$ = {3, 1, 4, 1, 5, 9, 2}. Prepend the sequence with the number $1$ so that you get {1, 3, 1, 4, 1, 5, 9, 2}. Then plug it ...
3
votes
1answer
645 views

Elementary proof that $3$ is a primitive root of a Fermat prime?

The following is exercise 6 of Chapter 4 in Ireland and Rosen's Number Theory. If $p=2^n+1$ is a Fermat prime, show that $3$ is a primitive root modulo $p$. I first recall that any Fermat prime ...
2
votes
2answers
169 views

Greatest common divisor problem

For fixed integers $a,b$, how can I find all integers $r$, $1\leq r\le a$, such that $\gcd(a,r)\text{ divides } b$? That is, I need an efficient way of finding those integers $r$.
0
votes
1answer
342 views

Sum of consecutive sub-sequence of 100 natural numbers divides 100 (equals 0 mod 100) [duplicate]

Possible Duplicate: pigeonhole principle and division I need a little help in an exercise. Given 100 natural numbers $a_{1},..,a_{100}$ , prove that there is a consecutive sub-sequence ...
2
votes
1answer
159 views

solution to linear congruence

I have the following relations $$a x \equiv b \pmod m\;\;,\;\; m y\equiv b \pmod a$$ Now, I need to find the minimum possible positive values for $x$ and $y$. Extended Euclid Algorithm doesn't ...
3
votes
2answers
446 views

Fibonacci / Lucas Numbers Relationship: $F_{2n} = F_n L_n$

Prove the identity by induction: $$ F_{2n} = F_n L_n, $$ where $F_n$ and $L_n$ are the $n^{th}$ Fibonacci and Lucas number, respectively. I have an answer but am not happy with it since it doesn't ...
1
vote
1answer
90 views

Pat the mathemagician

Pat the Magician asks a member of the audience to write a 13-digit number on the blackboard, while Pat is blindfolded. Pat then asks the volunteer to reverse the digits of the number, and to subtract ...
0
votes
2answers
358 views

Determine the remainder when $2^{1930}$ is divided by $840$

Determine $\Phi(840)$. Hence, determine the remainder when $2^{1930}$ is divided by $840$. I determined $\Phi(840) = \Phi(2^3*3*5*7) = 480$, however I don't know how I can use this to solve the ...
0
votes
2answers
191 views

What is the total number of zeroes in n!?

What is the total number of zeroes in $n!$? I do not want to know the number of trailing zeroes in $n!$. Let us take an example to understand what I want to know. $7! = 5040$. The number of ...
2
votes
1answer
102 views

Occurrences of a residue when reducing the multiplication table mod $a$.

Consider the following diagram of numbers. $$\begin{pmatrix}1 & 2 & 3 & 4 &.... & a \\ 2 & 4 & 6 & 8 & .... &2a \\ 3 & 6 & 9 & 12 & .... & ...
1
vote
1answer
95 views

Do all natural numbers appear in the digits of a normal number?

A normal number is a number where no number is favored to appear in the digits. Does this definition imply that all whole numbers appear in its digits? Because the definition involves notions from ...
3
votes
3answers
175 views

simple congruence system problem.

This is excercise 1 in George E. Andrews number theory. page 51. How am i supposed to solve this? Thanks very much in advance. I used the cancellation law to get isolate the x. But I don’t know what ...
7
votes
1answer
206 views

Deriving Fermat's little theorem from $(a+1)^p\equiv a^p+1$ modulo $p$?

It is known that $p$ divides the binomial coefficient $\binom{p}{i}$ for $1\leq i\leq p-1$. So from the binomial theorem, it is not hard to see $ (a+1)^p\equiv a^p+1 $ modulo $p$. Is there a way to ...
2
votes
1answer
155 views

If $\{a_1,\dots,a_{\phi(n)}\}$ is a reduced residue system, what is $a_1\cdots a_{\phi(n)}$ congruent to?

I'm trying work on problem 11 of Chapter 3 in Ireland and Rosen's Number Theory. Suppose $\{a_1,\dots,a_{\phi(n)}\}$ is a reduced residue system modulo $n$. Let $N$ be the number of solutions to ...
4
votes
2answers
283 views

Transform system of linear congruences to make use of Chinese Remainder Theorem

The following system of linear congruences in its given form cannot be solved using the Chinese Remainder Theorem. Can you help me transform the system sufficiently such that the Chinese Remainder ...
3
votes
2answers
116 views

Calculating that 13 is a Wilson Prime

I'm confused by the idea of a Wilson Prime. The theorem states that $$p^2=(p-1)!+1$$ This makes sense for $5$: $$5^2=(4\times3\times2)+1$$ so $5^2=25$ But it makes no sense to me for $13$: ...
6
votes
1answer
720 views

Product of three consecutive positive integers is never a perfect power

I am trying to prove that the product of three consecutive positive integers is never a perfect power. Can anyone point to gaps in my proof and/or post an alternate solution? Let the three ...
0
votes
3answers
1k views

Prove that if $d$ divides $n$, then $2^d -1$ divides $2^n -1$

Prove that if $d$ divides $n$, then $2^d -1$ divides $2^n -1$. Use the identity $x^k -1 = (x-1)*(x^{k-1} + x^{k-2} + \cdots + x +1)$
6
votes
1answer
188 views

Find all numbers $p$ such that all six numbers $p$, $p+2$, $p+6$, $p+8$, $p+12$, $p+14$ are primes

Find all numbers $p$ such that all six numbers $p$, $p+2$, $p+6$, $p+8$, $p+12$, $p+14$ are primes I know that $p=5$ works, but I don't know how to find all values for $p$, if any?
4
votes
2answers
237 views

Is this proof, that $\sqrt{n}$ is irrational for all non-square $n \in \mathbb{N}$, correct or not?

Prove that the square root of all non-square numbers $n \in \mathbb{N}$ is irrational I have made an attempt to prove this, I don't know if it's correct though: Take a non-square number $n \in ...
4
votes
3answers
270 views

How to find this GCD?

How to find GCD of $2n + 3$ and $5n^2 + 3n -1$ (depending on $n$) Thanks in advance!
17
votes
2answers
783 views

Large integer help

The integer $5685858885855807765856785858569666876865656567858576786786785^{22}$ has 6436343 divisors. Using only a scientific calculator, find a way to show it has exactly 5 prime divisors.
1
vote
1answer
136 views

Explanation for a peculiar property of a number

I had come across a problem, where 2 people play a game where think of a number n, and turn by turn subtract a number $p$ from $n$ where $p$ is a prime and is $p < n$ and 1 is taken as prime here. ...
0
votes
1answer
83 views

A question on divisibility 2

If, in my past question, $(2^{2m+1}-1)(2^{4m+2}+1)\mid (2^{2n+1}-1)(2^{4n+2}+1)$, then what is the relationship between $m$ and $n$?
2
votes
2answers
118 views

If $m,n\in\mathbb{N}$ and $f(m)|f(n)$ for the $f$ given below, must $m=n$?

If for two natural number $m$ and $n$, $(2^{2m+1}-1)2^{4m-2}(2^{2m+1}+2^{m+1}+1)\mid(2^{2n+1}-1)2^{4n-2}(2^{2n+1}+2^{n+1}+1)$, then $m=n$?
3
votes
1answer
134 views

solutions of consecutive integers observations

I wonder that, I made these observations from my previous study on product of consecutive integers. I am looking the solutions of these kind of equations. $(1)$ Is ...
2
votes
3answers
131 views

Solutions for $ 2^i = 3^ j - 1 $ or $ 2^i = 3^ j + 1 $

Are there any solutions for $ 2^i = 3^ j - 1 $ or $ 2^i = 3^ j + 1 $, for $i>3$ and $j>2$ ? Thanks! $:)$
0
votes
2answers
120 views

Derive a simpler expression for $\gcd(a+b,\text{lcm}(a,b))$?

Let $a$ and $b$ be two positive integers, such that neither $a$ nor $b$ is divisible by a perfect square. Is there be a simplified formula for $$\gcd(a+b,\text{lcm}(a,b)) ?$$ and is there a way to ...
2
votes
1answer
167 views

Solutions of Diophantine equations in Natural numbers

The one of solution of $x^4 - 2y^2 = -1$ is $x = 1$ and $y = 1$. However, the solution $(1, 1)$ of $x^4 - 2y^2 = 1$ is failed. We know $x = 1$ and $y = 1$ is small integers and we can check by trail ...
0
votes
5answers
402 views

How can I algebraically prove that $2^n - 1$ is not always prime?

This question is from Elementary Number Theory by W. Edwin Clark. Is $2^n - 1$ always prime, or not? Prove. Is this a start? $x^n - 1 = ( x - 1)(1 + x + x^2 \cdots x^{n - 1})$. So, $2^n - 1 = ...
4
votes
4answers
299 views

Integers that satisfy $a^3= b^2 + 4$

Well, here's my question: Are there any integers, $a$ and $b$ that satisfy the equation $b^2$$+4$=$a^3$, such that $a$ and $b$ are coprime? I've already found the case where $b=11$ and $a =5$, but ...
4
votes
2answers
183 views

Does this equation have integer solutions

Let $g\geq 2$ be an integer. (It will be the genus of some curve.) Are there positive integers $d$ and $e$ such that the equality $$ (e-2)(e-1) = 2d(g-1)+2$$ holds?
3
votes
2answers
265 views

Four digit reversal numbers

How to prove without an exhaustive checking that there are only 2 (nontrivial) four digit reversal numbers?
46
votes
10answers
3k views

Given real numbers: define integers?

I have only a basic understanding of mathematics, and I was wondering and could not find a satisfying answer to the following: Integer numbers are just special cases (a subset) of real numbers. ...
2
votes
1answer
113 views

Find b such that $(a+b)^3 - a^3=2007h$

Find all $b$ such that $(a+b)^3 - a^3$ divisible $2007\ (a,b \in \mathbb{Z})$ I can solve for $b$: $(a+b)^3 - a^3=2007h \rightarrow b=\sqrt[3]{a^3+2007h}-a$
49
votes
7answers
8k views

Prove every odd integer is the difference of two squares

I know that I should use the definition of an odd integer ($2k+1$), but that's about it. Thanks in advance!
0
votes
3answers
2k views

If an integer is divisible by 8 and 15, then the integer also must be divisible by which of the following?

I'm not going to list the choices here, mainly because I just want the general idea. If I generalize the question and was given $n$ different integers divide some integer $r$, how do I determine what ...