# Tagged Questions

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

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 ...
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 ...
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?
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 ...
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 ...
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 ...
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 ...
60 views

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 ...
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: ...
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$.
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 ...
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 ...
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 ...
39 views

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 ...
92 views

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 $(... 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?$$ 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 ... 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\... 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 ... 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 ... 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$$... 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 ... 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 ... 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 ... 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. 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=8kx=\frac{8k}{5}$$Does x=\... 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. 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? 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 ... 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$$... 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 ... 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 ... 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 ... 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 ... 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 ... 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 \...
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?