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

learn more… | top users | synonyms (1)

0
votes
1answer
59 views

Counting the number of integers less than $x$ that are relatively prime to a primorial $p\#$

Let $p \ge 5$ be a prime. Let $x \ge 20$ be an integer. Let $p\#$ be the primorial for $p$. Let $|\{ i \le x \, \wedge \gcd(i,p\#)=1\}|$ be the count of integers less than or equal to $x$ that are ...
5
votes
8answers
191 views

Prove with induction that $11$ divides $10^{2n}-1$ for all natural numbers.

$$10^{2(k+1)}-1 = 10^{2k+2}-1=10^{2k}\cdot10^{2}-1$$ I feel like there's something in that last part that should make it work, but I can't grasp it. Am I missing something obvious? Am I going in the ...
1
vote
5answers
217 views

How to prove that $42|a^7-a$? [duplicate]

Suppose we are given a number $a \in \mathbb{Z}$ prove that $42|a^7-a$. I'm not too sure how to start any ideas?
1
vote
2answers
34 views

Elementary number theory, concerning GCD

If I have two co-prime integers. $a, b$. Suppose that the product of these two integers is $c$. Further suppose that I have a further product of two co-primes, so $d = af$. Now if I multiply these ...
1
vote
2answers
32 views

Show that each $a_n$ is divisible by a prime which does not appear in the factorization of any $a_i$, i<n

Consider the sequence of integers $a_n$ defined recursively by $a_n=a_{n-1}a_{n-2}...a_0 + 1$ with $a_0=1$. Show that each $a_n$ is divisible by a prime which does not appear in the factorization of ...
1
vote
5answers
134 views

$n^2(n^2-1)(n^2-4)$ is always divisible by 360 $(n>2,n\in \mathbb{N})$

How does one prove that $n^2(n^2-1)(n^2-4)$ is always divisible by 360? $(n>2,n\in \mathbb{N})$ I explain my own way: You can factorize it and get $n^2(n-1)(n+1)(n-2)(n+2)$. Then change the ...
1
vote
5answers
250 views

Euclid's proof of infinitude of primes.

http://en.wikipedia.org/wiki/Euclid's_theorem I just read Euclid's proof for the existence of infinitely many primes (I have never used his proof earlier to prove this). It seems to me that he ...
3
votes
1answer
60 views

About Descartes numbers

I just have a quick question regarding the definition of Descartes numbers, otherwise known as spoof odd perfect numbers. In this Wikipedia page, Descartes numbers are defined as follows: A ...
0
votes
1answer
52 views

A question regarding the greatest common divisor

Good day to everyone! I just have a quick question regarding the greatest common divisor function. Say I have $\gcd(m,n^2)=1$. Does it follow that $\gcd(m,n)=1$? Here is my attempt at a proof: ...
0
votes
1answer
353 views

Prove that if n is a natural number and if n has a rational square root then in fact the square root of n is an integer [duplicate]

$n = (\frac{a}{b})^2$, where $a$ and $b$ have no common divisors. This yields $nb^2 = a^2$ $ra^2b^2 = a^2$ (because $n = ra^2$) I don't understand why $n$ is equal to $ra^2$.
1
vote
1answer
67 views

Reducing modulo powers of a prime

If p is an odd prime and a is coprime to p, how would one go about reducing $a^{p^{k-1}}\mod p^k$? Using Euler's formula we can get a value for $a^{p^{k-1}(p-1)}\mod p^k$ but I can't really see how ...
2
votes
3answers
143 views

Integer solution to $19x^3-84y^2=1984$

Show that there exist no integer values $x,y$ such that $19x^3-84y^2=1984$. Please help me in understanding no solution problems. I tried to check the modulo $7$ of both sides but couldn't reject ...
0
votes
0answers
47 views

find all primes $p$ such that $a^p-1$ has a primitive factor.

We say that a prime $q$ is a primitive factor of $a^n-1$ if $q|a^n-1$, but $q$ does not divide $a^m-1$ for any $m$ such that $0<m<n$. Given $a\ge2$, find all primes $p$ such that $a^p-1$ has a ...
0
votes
1answer
39 views

Is it true that (L\a + L\b,L) = 1. L=$lcm(a,b)$

Suppose $a$ is different from $b$ and $L=lcm(a,b)$.Is it true that (L\a + L\b,L) = 1$ ? How do I approach this one? Should I write the Bezout's Theorem??
1
vote
1answer
46 views

Find all primes of the form

Find all primes of the form $3\cdot2^{2^t-1}+1$. For $t=1$ it works.And I was thinking that it should have some logic because the other numbers go really large and is meaningless to take them one by ...
0
votes
1answer
48 views

*length* of the longest sequence of consecutive square-free integers

It may seem like a duplicate question but I am looking for the length of the longest sequence of consecutive square-free integers not to show that there exist.
1
vote
1answer
94 views

Is there a primality test based on the sum of squares of the first $n$ natural numbers $\sum_{x = 1}^{n} x^2$?

The Fibonacci and Catalan primality tests are based on the calculation of the congruences of those numbers versus the possible prime $n$ (the rules are different depending on the primality test), and ...
0
votes
2answers
101 views

Prove or disprove that every even integer is the difference of two squares. [duplicate]

I don't know where to start. Let $2k$ be an even integers and $a^2 - b^2$...
3
votes
3answers
111 views

Prove that if a set of even numbers do not divide into one another then doubling each of them preserves this property

Assume I have a list of even integers where none can evenly divide into any of others. Is it true that if I multiply them all by $2$ then they still cannot divide into each other? For example say my ...
1
vote
3answers
98 views

sums of squares and Pythagorean Triples

I'm told that if $r^2 + s^2 = z^2$ then $(r+s)^2 + (r-s)^2 = 2z^2$, which is obvious. But i'm trying to show that every integer solution to $x^2 + y^2 = 2z^2$ arises this way from a Pythagorean Triple ...
7
votes
2answers
106 views

Divisibility of $3^n-1$ by $2^n$.

It is a curious fact that $3^n-1$ is divisible by $2^n$ iff $n=1,2,4$. (It turns out to have applications in algebraic topology, differential topology and algebra.) Does anyone know of a very short ...
1
vote
1answer
29 views

$(a,bc)=\frac{(a,b)(a,c)}{(a,b,c)}$ : when is this gcd-identity true?

Let $a$, $b$ and $c$ be integers and let $(.,.)$ denotes the $\operatorname{gcd}$ function. When is this indentity true : $$(a,bc)=\frac{(a,b)(a,c)}{(a,b,c)} \quad ?$$ Many thanks !
1
vote
1answer
34 views

Modular arithmetic - Calculating a large power

This is from a contest. I am trying to solve: What is the largest power $n$ such that $7^{2048} - 1$ is divisible by $4^n$. So far I have been trying with $7^{2^{11}} \equiv 1 \pmod {2^{2n}}$ Then ...
0
votes
2answers
56 views

If $a=b+c$ then $(a,b)=(a,c)=(b,c)$

If $a=b+c$ then $(a,b)=(a,c)=(b,c)$ I was thinking of writing the Euclidean algorithm \begin{align*}a &= b\cdot 1+c\\ b &= c\cdot (-1) + (b+c)\\ c &= a \cdot 1 + (-b)\end{align*...
4
votes
1answer
122 views

If ${a}$ is an arbitrary integer, then prove that ${360|a^2(a^2-1)(a^2-4)}$.

I think I have solved the problem. I want to verify my proof, since I don't have a teacher to help me. Proof: Since, ${360=8*45}$ and ${gcd(45,8)=1}$, hence if we can prove that ${45|a^2(a^2-1)(a^2-...
-1
votes
1answer
32 views

If $n \in \mathbb{N}$ , not divisible by 3 show there $\exists t \implies 3^t < n < 3^{t+1}$

If $n \in \mathbb{N}$ , not divisible by 3 show there $\exists t \implies 3^t < n < 3^{t+1}$ By the division algorithm: $$n = 3a + r \implies 0 < r < 3$$ For some $a$ But I cannot do ...
3
votes
2answers
92 views

Why $\prod\limits_{n<p\le2n}p\le\binom{2n}{n}$

Why is for $p$ prime, $\prod\limits_{n<p\le2n}p\le\binom{2n}{n}$ I think induction doesn't work; the factor from $\prod\limits_{n-1<p\le2n-2}p\quad$ to $\prod\limits_{n<p\le2n}p$ can be $(...
1
vote
3answers
258 views

How can I prove $(a+b)\mod m = ((a \mod m) + (b \mod m)) \mod m$? [closed]

How Can I prove $$(a+b) \mod m = ((a \mod m) + (b \mod m)) \mod m?$$
0
votes
2answers
82 views

How to find positive integer solution of bilinear transformation?

Let $y = (ax + b)/(cx + d)$, where $a, b, c, d$ are known integer constants, is there any technique to find positive integer solution of $x, y$? is there any iterative method approach without using ...
1
vote
1answer
84 views

Restating a floor function as a finite sum

It seems to me that a floor function can be expressed as a finite sum that is open to the Möbius function. Does it follow for all nonnegative integers $a$ that: $$\left\lfloor\frac{a}{b}\right\...
6
votes
2answers
394 views

reversing digits and squaring

If we reverse the digits of $12$ we will get $21$. $12^{2}=144$. If we reverse its digits we will get $441$ which is $21^{2}$. Here is the puzzle. How many such two digit numbers are there? Digits ...
4
votes
3answers
120 views

$n(n+1)(n+2)$ is not a perfect power [duplicate]

We have $n,n+1, n+2 \in \mathbb Z^+$ Their product can't be a whole exponentiation. Why? I noticed that $gcd(n,n+1)=1$ and $gcd(n+1,n+2)=1$ This could be a good starting point in the proof. But ...
3
votes
0answers
122 views

How many distinct factors of $n$ are less than $x$?

For some (squarefree) integer $n$ and some integer $x$, I would like to find an expression that gives, for all $n$ and $x$, a good upper bound on the function $$f(n, x) = \sum_{d|n, d < x} 1$$ ...
1
vote
3answers
74 views

Number Theory: Divisibility

I'm really having some trouble figuring out these problems: Let $a,b \in \mathbb{Z}$ such that $14\mid (4a+3b)$. Prove or disprove $14\mid (30a-16b)$ Let $a,b \in \mathbb{Z}$, Prove if $a\mid b^2$ ...
2
votes
3answers
65 views

Prove that $\log_52$ is irrational

Prove that $\log_5(2) \in \mathbb{R}\setminus \mathbb{Q}$ (irrational numbers). I know there is a question out there already for this but my problem is that I need to prove this using the ...
0
votes
1answer
44 views

How many combinations can be made for the fraction?

Rational numbers, $a, b$ are chosen from the set of rational numbers. The condition is: $a, b \in [0, 2)$. $a, b$ can be written as: $a, b = \frac{n}{d}$, where $n, d$ are integers with: $1 \le d \le ...
-1
votes
4answers
128 views

How to prove it is always divisible by 6 [closed]

Prove that $n(n^2 − 7)$ for is always divisible by 6. (for any natural number $n$) I have no idea.
1
vote
1answer
98 views

find all integer $x$ such that $7x\equiv 2x$ (mod 8)

I am trying to find all integer $x$ such that $7x\equiv 2x$ (mod 8) First, I have $$ 7x-2x=8k \hspace{0.1in} (\text{where} \hspace{0.1in}k\in\mathbb{z}) $$ $$5x=8k$$ $$x=\frac{8k}{5}$$ Does $x=\...
1
vote
0answers
28 views

Addition of LCM

I come across the sum $\sum_{1}^{n/2} \operatorname{LCM}(i,n)$ Is there any fast way to get the solution of this sum? Any ideas that we can apply other than euclidean algorithm to find the solution.
1
vote
2answers
95 views

Prove ca ≡ cb (mod m) if and only if a ≡ b mod (m/gcd(c, m) )

I can't seem to answer this question without assuming that gcd(c,m) = 1. Is the question missing any information?
2
votes
5answers
96 views

Is there a way, in general, to tell whether the nth root of a integer is rational?

Is there a way, in general, to tell whether the $n^{th}$ root of a integer is rational? More explicitly, is it possible to elegantly determine whether the result of $k^{1/n}$ is rational for $k,n \in ...
1
vote
2answers
28 views

Greatest Commom Divisor

In my lecture notes there is the following: $$\newcommand{\gcd}{\operatorname{gcd}} a, b \in \mathbb{N}, \gcd(a, b)=d \implies \exists s, t \in \mathbb{Z} : sa+tb=d \implies tb \equiv d \pmod a$$ ...
2
votes
1answer
157 views

Why are there no continued fraction representation for $\pi$ obeying mathematical rules?

There are several irrational numbers that can be represented with continued fraction such that a mathematical rule arises in this continued fraction. For example, the Euler number $e$ can be ...
2
votes
2answers
131 views

Prove that even + odd is odd.

Prove that a even number + odd number = odd number Let $x$ be the even number, let $y$ be the odd number. From the definition of odd numbers, $y + 1$ is even. Let: $$x + y = z$$ Suppose $z$ is ...
2
votes
5answers
43 views

Prove that $m$ is an integer

Suppose $n$ is a odd integer. It satisfies: $$3^{s} < n < 3^{s+1}$$ For some integer $s \ge 0.$ Show that: $$m = \frac{n - 3^{s}}{2}$$ Is an integer. So, $$2m = n - 3^{s}$$ But that wont ...
0
votes
1answer
20 views

$ax\equiv b\pmod c$ is equivalent to $x\equiv rb\pmod c$

How are these $2$ equations equivalent ? If $\gcd(a,c)=1$, and $r,s\in\mathbb Z:ra+sc=1$ $ax\equiv b\pmod c\tag1$ and $x\equiv rb\pmod c\tag2$ Is there a mistake in the formula ? ($s$ doesn't ...
1
vote
6answers
108 views

If $n$ is an odd integer prove that $n - 2^k$ is divisible by $3$

So let $n$ be a odd integer. Show that $n - 2^k$ is divisible by $3$ if $k$ is SOME SPECIFIC positive integer. $k \ge 0$. So there only has to exist one. For example: $$7 - 2^2 = 3$$ is divisible by ...
0
votes
1answer
65 views

How to proof this congruence relation?

While looking for a way to calculate last digits of exponential towers of $3$ I stumbled upon this odd little conjecture and can't really find a way to proof it: For every $k>1$ and $n, k \in \...
2
votes
2answers
82 views

Extension of Fermat's Little Theorem

I just read about Fermats little theorem and was wondering if the following relationship is an extension of this: $7^{8n+3}+2$ = 5p where p is an real integer. If so can you show me how/why this is?
4
votes
2answers
137 views

Frogs and switches - problem solving strategies

The question is pretty simple, consider 1000 switches and 1000 light bulbs, every time we press a switch it's light bulb changes it's state(ON to OFF and vice versa). We start with all the light bulbs ...