1
vote
1answer
25 views

Something similar to Euler's theorem

If $p$, $q$ are not equal primes. $n=pq$, $\varphi(n) = (p − 1)(q − 1)$, $d = \gcd(p − 1, q − 1)$. Is it true that for any $a$ such that $\gcd(a, n) = 1$ holds $a^{\frac{\varphi(n)}{d}} \equiv 1 ...
0
votes
1answer
21 views

Find all $(h,k)$ such that $2^h \equiv 1 ~(\text{mod}~ 3^k) $

I'm facing with the following problem: Find all $(h,k)$ such that $$2^h \equiv 1 ~(\text{mod}~ 3^k) ~~~~~~~~(1)$$ and $$2^h \geq 3^k+1 ~~~~~~~~(2).$$ I'm just able to prove that the $(1)$ holds ...
2
votes
3answers
57 views

$\dfrac1a+\dfrac1b=\dfrac1c$, $a, b, c \in \mathbb{N}$ with no common factor, find all solutions [duplicate]

Given $\dfrac1a+\dfrac1b=\dfrac1c$, where $a, b, c \in \mathbb{N}$ with no common factor, find all solutions. Actually, you can think this question as a follow up of this one. Today, I saw this ...
2
votes
1answer
22 views

If (a,b) = 1 and c|(a+b), show that (a,c) = (b,c) = 1

I am working on this homework problem: If $\gcd(a, b) = 1$ and $c|(a + b)$, show that $\gcd(a, c) = \gcd(b, c) = 1$. Hint: Let $d = \gcd(a, c)$ and show that $d|\gcd(a, b)$. (An Introduction to ...
1
vote
2answers
23 views

How can I prove divisibility using congruence?

I'm new to this, so please excuse me if I said something wrong or offended anyone. We're doing the number theory in class, and I came across this question, which I had no idea how to even begin..: ...
2
votes
1answer
34 views

If $p$ is prime and $\sigma(p^k) = n$, then $p\mid (n-1)$

If $p$ is prime and $\sigma(p^k) = n$, then $p\mid (n-1)$. proof: Suppose $\sigma(p^k) = [p^{k+1} -1]/(p-1) = n$. Then $n-1 = [p^{k+1} -1]/(p-1) - 1= [p^{k+1} -1 - (p-1)] /(p-1) = [p^{k+1} - ...
3
votes
3answers
96 views

when ${\rm gcd} (a,b)=1$, what is ${\rm gcd} (a+b , a^2+b^2)$?

I want to prove above statement "what is ${\rm gcd} (a+b , a^2+b^2)$ when ${\rm gcd}(a,b) = 1$" I've seen some proofs of it, but i couldn't find useful one. here is one of the proof of it. some ...
0
votes
2answers
45 views

If $c | ab$, then $c | a$ or$ c | b$

I need help proving/disproving the implication, If $c | ab$, then $c | a$ or $c | b$ So far, I got Assume $c | ab$ then $ab= cl$ for some integer $l$ Now what should my next step be?
2
votes
1answer
45 views

Divisibility Property

I am trying to justify the following result: Let $p,q$ be integers such that $GCD(p,q) = 1$. Then for all $n \in \mathbb{N}$ exists an integer $j_n$ such that $q^{j_n}t = t \ (mod \ p^{2n+1}), \ ...
4
votes
5answers
97 views

Show that $\gcd(a,b)>1$

Given are three natural numbers $a$, $b$ and $c$, for which $$\frac1a+\frac1b=\frac1c$$ Show that $\gcd(a,b)>1$. Could you someone provide a hint? I already tried algebraic manipulation, but I ...
10
votes
1answer
126 views

Does there always exist an even $m$ that is a multiple of exactly $n$ of the numbers $1$, $2$, …, $2n$?

Let $n>1$ be a positive integer. Then there exists a positive integer $m$ such that exactly half of the numbers $1$, $2$, $\ldots$, $2n$ divides $m$: one can take $m = (2n-1)!! = (2n-1) \times ...
2
votes
3answers
105 views

Prove or disprove $ p^{r+s}\mid q^{ke} - 1 \iff p^s \mid k$.

Let $p$ be an odd prime and $q$ be a power of prime. Suppose $e := \min\{\, e \in \mathbb{N} : p \mid q^e - 1 \,\}$ exists. Put $r := \nu_p(q^e - 1)$ (that is, $p^r \mid q^e - 1$ and $p^{r+1} \nmid ...
1
vote
3answers
98 views

Sum of the digits

Let $N$ be the greatest number that will divide $1305,4665$ and $6905$, leaving the same remainder in each case. Then what is the sum of the digits in $N$?
1
vote
0answers
19 views

Sequence terms being divisible

Here's a question I would like hints for: The sequence ${x_n}$ is defined by $x_{n+2}=6x_{n+1}-9x_{n}$ for $n \geq 0$ where $x_0=3$ and $x_1=18$. What is the smallest $k$ such that $x_k$ is ...
0
votes
0answers
10 views

determining no of divisor of quotient '$Q$'

i want to determine number of '$k$'($1 \leq k \leq n$) such that if i divide '$n$' with 'k' then quotient is '$Q$'. for example: $n=5$ and $Q=2$ then ans$=1$ because for only $k=2$ ,$ \frac{n}{k}=Q$. ...
0
votes
0answers
16 views

Problems on Divisability

Consider the following problem If $k-1$ divides $n-1$, $k(k-1)$ divides $n(n-1)$, $n = r$ mod $k$ Find the smallest value m>n such that $k-1$ divides $m-1$ and $k$ divides $m$
2
votes
2answers
25 views

Question about G.C.D.

Let, $$a_{n}=n^2+20$$ $$d_{n}=\gcd(a_{n},a_{n+1})$$ where $n$ is a positive integer. Find the set of all values attained by $d_{n}$ I tried, $d_{n}=\gcd(n^2+2n+21,n^2+20)$ ...
5
votes
1answer
89 views

If $a^n-1$ is divisible by $b^n-1$ for all $n$, then $a$ is a power of $b$

Let $a,b$ be natural numbers not equal to $1$ such that $\frac{a^n-1}{b^n-1}$ is natural for any natural $n$. Prove that $a=b^m$ for some natural $m$.
2
votes
0answers
35 views

Is there a cycle for modulo operation on a floor?

I have a floor $${\left\lfloor\frac{n}{i}\right\rfloor},$$ where i varies from 1 to n (n can be upto $10^{10}$), and there's another number given 'm' (m upto $10^{5}$). Does ...
3
votes
1answer
63 views

Greatest common divisor problem involving $a^p+b^p$ [closed]

Let $\gcd(a,b)=1$ for some $a,b\ \epsilon \ \mathbb{N}$. Prove that for any odd prime p: $$\gcd\left(a+b,\frac{a^p+b^p}{a+b}\right)=1,~~~~ \text{or} ~~~p.$$
0
votes
0answers
21 views

Could you give a definition of what is a superior highly composite number using only words?

I know very well what is a superior highly composite number, but I would like to see how could we (roughly) define what is a superior highly composite number using only words (using no equations and ...
0
votes
1answer
24 views

number system and divisibility

could anyone please find a solution to that problem: $b$,$c$,$d$ are consecutive even integers such that $2\lt b \lt c \lt d$. what is the largest positive integer that MUST be a divisor of $bcd$?
2
votes
1answer
45 views

Determine the divisibility of a given number without performing full division

My question is slightly more complicated than what's implied on the title, so I will start with an example. Given any number $N$ on base $10$, we can easily determine whether or not $N$ is divisible ...
2
votes
0answers
18 views

How to know if the number of divisors in a determined range for a number is odd or even [duplicate]

I would like to know if the number of divisors for the number in a determined range is odd or even without counting the divisors, I think the question is a little tad fuzzy, thus, I will supply the ...
4
votes
1answer
138 views

Relationship between Primes and Fibonacci Sequence

I recently stumbled across an unexpected relationship between the prime numbers and the Fibonacci sequence. We know a lot about Fibonacci numbers but relatively little about primes, so this connection ...
10
votes
3answers
2k views

Why are all non-prime numbers divisible by a prime number?

In Euclid's infinite prime numbers proof, the logic is as follows: Assume a set $S$ of all prime numbers in existence is finite (there are a finite amount of primes) Then there must be a greatest ...
2
votes
1answer
49 views

Silly number theory questions I can't prove.

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+bs$, if I am restricted to $a,b \in \mathbb{N}$? To be more specific, I ...
4
votes
2answers
87 views

A non-UFD such that $a^2 \mid b^2$ does not lead to $a\mid b$

Is there any non-UFD that is a commutative ring such that $a^2 \mid b^2$ does not always lead to $a\mid b$? It would be preferable if examples are something that does not involve ...
2
votes
1answer
101 views

When does $2^n+n \mid 8^n+n$?

How to find all positive integers $n$ such that $2^n+n$ divides $8^n+n$ ?
9
votes
1answer
102 views

For what integers $n$ is this divisibility statement true?

The statement being $$n^2 + 2 \mid 2014n + 2$$ The answer is $n = -2, 0, 1, 2014$. Don't know how to arrive at this answer without using comp sci. (Using the compsci answer, we can restrict the ...
2
votes
1answer
41 views

How prove $n|2^{\frac{n(n-1)}{2}}\cdot (2-1)(2^2-1)(2^3-1)\cdots (2^{n-1}-1)$

Question: Today, when I solve other problem, I found this follow interesting result $$n\mid\left(2^{\frac{n(n-1)}{2}}\cdot (2-1)(2^2-1)(2^3-1)\cdots (2^{n-1}-1)\right),n\ge 1$$ It is clear ...
1
vote
1answer
244 views

Is there a simple algorithm I can use for this?

if I were asked to find all integers between 1 and 100 that leave remainder 3 on division by 5 and leave remainder 4 on division by 7, how would I go about this? It seems like such a simple question ...
3
votes
1answer
305 views

Choose a k-subset such that its elements 's gcd is maximal

Given $n$ positive integer and a positive integer k. How to find a subset of size k such that its elements 's gcd is maximal (just give the maximum value of gcd is okay). Example: Give $3$ integers ...
3
votes
4answers
66 views

Proving that (4-2/1)(4-2/2)…(4-2/n) in an integer.

We have to prove that $(4-2/1)(4-2/2)...(4-2/n)$ is an integer for $n\in\mathbb{N}$. Can we do this by induction? We prove for $n = 1$, which is trivial as $(4-2/1) = 2$ which is clearly an integer. ...
3
votes
2answers
65 views

Induction on GCD problem [duplicate]

This is a two part question Given $\gcd(a,b) = 1$ consider $$\gcd \left( \frac{a^n - b^n }{a-b}, a- b\right) $$ It appears that the value of this is always equal to $n$ or $1$. How to prove it? ...
1
vote
0answers
37 views

A Question Related to Zsigmondy's Theorem

I am wondering if there is a way to prove the following statement, which bears some resemblance to Zsigmondy's Theorem. I am not sure if the statement is true, but it seems as though it should be. ...
1
vote
0answers
49 views

$U(n) =$ the smallest strictly positive integer $k$ such that $2^k-1$ is divisible by the first $n$ primes. What are the first values of $U(n)$?

$U(n) =$ the smallest strictly positive integer $k$ such that $2^k-1$ is divisible by the first $n$ prime numbers (except for the first prime number: $2$). What are the first values of $U(n)$ up to ...
0
votes
1answer
54 views

Parity of number of factors up to a bound?

Consider $b,n\in\mathbb{N}$ where $b\leq n$. We want to find the parity (ie. odd or even) of the number of divisors of $n$ that are $\leq b$. The question is to find a fast algorithm to find that ...
3
votes
1answer
96 views

Probability that two random integers have only one prime factor in common

The probability that two integers picked at random are relatively prime is known to be $1/\zeta{(2)}=6/\pi^2\approx0.607927...$. Generalizing, the probability that $n$ random integers have $\gcd=1$ is ...
0
votes
2answers
404 views

Finding Coprime triplets

Given a sequence a1, a2, ..., aN. Count the number of triples (i, j, k) such that 1 ≤ i < j < k ≤ N and GCD(ai, aj, ak) = 1. Here GCD stands for the Greatest Common Divisor. Example : Let N=4 ...
6
votes
1answer
49 views

Sequences where each number is a divisor of one less than the next

Let $N,k$ be fixed. Call a sequence of positive integers $a_1,a_2,\dots,a_k$ good if for each $i$, $a_i$ is a divisor of $a_{i-1}-1$. Consider the set $$S = \{a_i : a_1,\dots,a_k \text{ is a good ...
3
votes
1answer
64 views

If $k$ is an odd number then $3k^2 +16$ is not a perfect cube

I am pretty sure that the title is true. Could anybody please prove it? I am particularly interested in a proof that mostrly relies on divisibility.
1
vote
3answers
54 views

Prove that $(k.n)!$ is divisible by $(k!)^n$

Suppose $k,n$ are integers $\ge1$. Show that $(k.n)!$ is divisible by $(k!)^n$ I have simplified the problem and now, I need to prove that any $k$ consecutive integers is divisible by $k!$. However I ...
1
vote
2answers
81 views

Solving $a^2+b^2\equiv 0$ mod $c$ for distinct integers $a,b,c$ constrained between two consecutive squares

Show that for any natural number $n$, between $n^2$ and $(n+1)^2$ one can find three distinct natural numbers $a,b,c$ such that $a^2+b^2$ is divisible by $c$. A friend and I found a general case that ...
0
votes
1answer
39 views

What are the smallest numbers $n$ such that $\dfrac{d(n)}{\ln(n)} \geq k$ where $d(n) = \sigma_0(n)$ is the number-of-divisors function?

I have calculated $\dfrac{d(n)}{\ln(n)}$ on a few highly composite numbers up to 5040. Here is what I got: $\dfrac{d(120)}{\ln(120)} = 3.3420423$ $\dfrac{d(360)}{\ln(360)} = 4.0773999$ ...
0
votes
1answer
50 views

Remainder of trick-number divided by 9

How can I calculate the remainder of something like $199\cdot 741934^{1234}$ by 9?
0
votes
2answers
131 views

Prove that if $n^2 - 1$ is divisible by a prime number $p$ such that $n - 1$ is not divisible by $p$, then $n + 1$ is also divisible by $p$.

If this proposition is false, please give at least $3$ counter-examples, and try to modify the proposition so that it becomes true. If the proposition is true, please try to prove this even more ...
2
votes
3answers
162 views

Find positive integers $(x,n)$ such that $x^{n} + 2^{n} + 1$ is a divisor of $x^{n+1} +2^{n+1} +1$

Find all positive integers $(x,n)$ such that $x^{n} + 2^{n} + 1$ is a divisor of $x^{n+1} +2^{n+1} +1$ I encountered this question in one of my monthly assignments. Unfortunately, I don't know ...
2
votes
2answers
115 views

Greatest common divisor with one parameter and condition

I have this homework question: Find $d = \gcd(10x+6, 3x+1) $ where $d > 5$ and $x$ is natural How can I solve it?
0
votes
1answer
103 views

Why does the number of divisors of a superior highly composite number is always a highly composite number up to 720720 ? (the only exception is 120)

I've calculated the number of divisors of every superior highly composite number up to $10^{27}$: http://oi59.tinypic.com/ndaijo.jpg The number of divisors of a superior highly composite number is ...