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

learn more… | top users | synonyms (1)

0
votes
0answers
21 views

congruences: number theory

We have the following Diophantine equation on l, m, n(all belong to natural number) (4a^2 - y^2)^l + (4ay)^m = (4a^2 + y^2)^n, where a, y both belong to natural number with (a, y) = 1, 2a > 1, y is ...
-1
votes
0answers
15 views

number theory: congruences [on hold]

if a is odd, m is congruent to n (mod 2) and m is mot equal to 1. This implies that n is even. How it happens? Given equation is (4a^2 - y^2)^l + (4ay)^m = (4a^2 + y^2)^n where a, y belong to natural ...
1
vote
3answers
61 views

Finding GCD of $95$ and $39$

My Algebra instructor gave us this problem which is to find gcd of $95$ and $39$ and express it as $95x+39y$. Also are $x$, $y$ unique? Now they are relatively prime so GCD is $1$. I have no clue ...
5
votes
0answers
45 views

An observation regarding the divisors of Euler's totient function

I observed that if $n$ is a composite number of the form $6k + 1$ then there are at least three divisors of $n - 1$ which do not divide $\phi(n)$ (Euler's totient function). Is this true in general?
5
votes
3answers
61 views

Find $2$ to the power $p^2-1$ modulo $p$

Given a prime number $p>2$, find $2^{p^2-1}$ modulo $p$. I know Fermat's and Euler's theorem but I can't apply them here. Any help would be grateful.
0
votes
0answers
34 views

New Criterion to Carmichael Numbers

Can anyone prove the following: If $p$ $=$ $a*b*c$ is a Carmichael Number, and the lcm (least common multiple) of ($a-1$), ($b-1$), and ($c-1$) is $m$, prove ($p-1$)/$m$ is prime. (This applies to ...
2
votes
2answers
59 views

$2^{n!}\bmod n$ if $n$ is odd

Given an odd number $n$, find $2^{n!}\bmod n$ and what if $n$ is even? I am not getting how to deal with that $n!$ in the power of $2$. Any help will be truly appreciated.....
1
vote
2answers
91 views

How many zeros are there in $25!$? [duplicate]

How many zeros are there in $25!$? I don't know how to really calculate it the number of zeros in the right hand can easily find by Legendre's formula. That gives us: $\lfloor{\frac{25}{5}}\rfloor+\...
0
votes
1answer
25 views

Is it possible to predict the digit sum of two factors by the product's digit sum?

Let's say we have a number that is the product of exactly two prime numbers, for example: 143 = 11*13 The digit sum of the product correlates with the digit sum of the factors: Digit sums: DS(...
0
votes
1answer
30 views

Prove that $n^7$ = n(mod 42) [duplicate]

We have to prove $n^7$ = n(mod 42) i tried as We know $n^7$-n is divisible by 7 Hence n(n-1)(n+1)(n$^2$ +1 +n) is divisible by 7
-1
votes
2answers
64 views

Let $A=\{1,2,3,…,2^n\}$. Consider the greatest odd factor of each element of A and add them… [on hold]

Let $A=\{1,2,3,...,2^n\}$. Consider the greatest odd factor (not necessarily prime) of each element of A and add them. What does this sum equal?
2
votes
1answer
67 views

Riemann Hypothesis and $\sum\limits_{k\leq n}\left(\frac{\mu(k)}{k}\right)^2$

I know that Riemann Hypothesis is equivalent to the following statement $\sum\limits_{k\leq n}\frac{\mu(k)}{k}=O(n^{-1/2+\epsilon})$ Is there any relation between Riemann Hypothesis and $\sum\...
1
vote
2answers
55 views

If $a$ and $b$ are whole numbers from $1$ to $100$, how many pairs of numbers $(a,b)$ are there which satisfy $a^{\sqrt{b}}=\sqrt{a^b}$

If $a$ and $b$ are whole numbers from $1$ to $100$, how many pairs of numbers $(a,b)$ are there which satisfy $a^{\sqrt{b}}=\sqrt{a^b}$ This was from a math contest I did earlier today and I was ...
1
vote
0answers
31 views

Concerning Arithmetic Progressions

Let p and q be two consecutive prime numbers. Let there be two arithmetic progressions whose initial terms differ by 2. Let both arithmetic progressions have the same common difference. Let the ...
0
votes
1answer
27 views

How can you solve this type of (not quite linear) diophantine equation in 2 variables?

Is there a general technique to find solutions of this type of equation? 555555=t+2rt+r I'll provide the only answer I know in the comments. Thanks.
-1
votes
0answers
16 views

Proof that a binary adder can be used to perform an n-bit unsigned subtraction

A n-bit binary adder can be used to perform an n-bit unsigned subtraction operation $X - Y$, by performing the operation $X + Y + 1$, where $X$ and $Y$ are n-bit unsigned numbers and $Y$ (with a bar) ...
1
vote
0answers
37 views

How to find the first integer making two progressions have gcd $> 1$

Is there a technique to efficiently find the first positive integer, $r$, that makes: $$\gcd(97+r, 106-r) > 1\text{?}$$
1
vote
1answer
30 views

Locating the double of a number in a triangular arrangement of the integers?

I write the positive numbers starting at $1$ in a triangle:$$\mathbb{N}_\triangle = \begin{matrix} &&&&&21&\ldots \\ &&&&15&20&\ldots ...
-4
votes
0answers
51 views

The smallest even/odd integers such that $\sum_{k=1}^nk$ is a square

Let m be the smallest odd positive integer for which 1 + 2 + ··· + m is a square of an integer and let n be the smallest even positive integer for which 1 + 2 + ··· + n is a square of an integer. What ...
1
vote
2answers
90 views

Solve the equation $1-x+x^{2}-x^{3}+x^{4}=y^{4}$ in $\mathbb{Z}$

I am working on the following exercise. Solve the equation $1-x+x^{2}-x^{3}+x^{4}=y^{4}$ in $\mathbb{Z}$. I have a couple of ideas for going about this exercise. $1)$ By moving $1$ to the other side ...
5
votes
0answers
56 views

Interesting property of Fibonacci numbers

Let we have an integer number $m$ such that $p \mid m \implies (p^2-1) \mid m$ for any prime divisor $p$ of $m.$ Prove that for such $m$ we have $F_{n+m}=F_{m} \mod m $ for any $n>1.$ Any ideas ...
1
vote
0answers
34 views

How often is $k, 2k, 3k…$ modulo $n$ less than $b$ before it hits $-1$?

Let $n$ and $k$ be coprime, and let $1\leq b \leq n$. The sequence $k, 2k ,3k, \ldots$ reduced modulo $n$ to the range $1, \ldots, n$, will eventually run through every integer in the range $1, \ldots,...
2
votes
2answers
60 views

year 10 factorial question

I would like to know the number of zeros occuring in the factorial of 2016? (2016!) I have read some ways but i don't understand it.
0
votes
2answers
73 views

Show that no integer of the form $a^3 +1$ is a prime for $a>1$ [duplicate]

Can someone please solve this and explain the steps taken to reach this solution ?
1
vote
2answers
62 views

“if $n$ is a composite integer, then $n$ has a prime factor not exceeding ${\sqrt n}$” - proof explanation

the proof of this theorem was as follows: since $n$ is composite, then $n=ab$, where $a$ and $b$ are integers with $1\lt a \le b \lt n$. Suppose now that $a \gt {\sqrt n}$, then $${\sqrt n} \lt a \...
3
votes
4answers
43 views

On the kernel of a certain module epimorphism $\mathbb{Z}^2 \to \mathbb{Z}/6\mathbb{Z}$

In order the construct a certain projective resolution of $\mathbb Z / 6 \mathbb Z$ I need to find the kernel of the ($\mathbb Z$-) module morphism: $$\epsilon_0 : \mathbb Z^2 \to \mathbb Z / 6 \...
1
vote
3answers
180 views

Is “$x^2=1\implies x=\pm 1$” true on any field? why?

The only elements $x\in\Bbb F_p$ with $x^2=1$ are $\pm1$, right? Is that true for any field? How do I see that it's true?
0
votes
2answers
27 views

Can the set of uneven number be written as the intersection of two sets?

Let $U = \{ n \in \mathbb{N} | n \equiv 1 (2) \}$. My question is: Can we find two proper subsets $M,N$ of $\mathbb{N}$ such that $M \neq N$ and $M,N$ are not equal to $U$ and $U = M \cap N$? It ...
-2
votes
0answers
27 views

Combinatorical problem [on hold]

$k$ is a natural constant.Determine $x,y,z$ knowing that $\binom{z+k}{x+y} + \binom{z}{x} \le k$ and $2x+y \le z$.
-3
votes
0answers
34 views

Comp Questions-Enumeration, Rates, Numbers, Geometry [on hold]

For each integer from 0 to 999, Michael wrote down the sum of its digits. What is the average of the numbers that Michael wrote down? It takes Jacob one and a half hours to paint the walls of a room ...
4
votes
7answers
101 views

Prove that $p^2 - 4qr$ ($p,q,r$ odd natural numbers) is never a perfect square

The givens for the question: $p, q, r$ are odd natural numbers. We need to prove that $p^2 - 4qr$ is never a perfect square. Inspecting a few examples it seems to be true, but I have no idea where to ...
1
vote
1answer
63 views

How many solutions does $x^2 = 1$ have in $\mathbb{Z}/m\mathbb{Z}$ in general? [on hold]

As the title suggests, how many solutions does $x^2 = 1$ have in $\mathbb{Z}/m\mathbb{Z}$ in general?
2
votes
4answers
37 views

Problem in Divisibility and Functions

Suppose that $ n $ is an integer, $ A $ is the set of $ n $'s divisors and $ f :A\rightarrow A $ be a function with this property: if $ a $ and $ b $ belong to $ A $ and $ a\mid b $, then $ f (a)\mid ...
4
votes
1answer
47 views

Two questions on the Gaussian integers [duplicate]

I have two questions on the Gaussian integers. Is any element in $\mathbb{Z}[i]$ the root of a monic polynomial with coefficients in $\mathbb{Z}$? Conversely, does any element in $\mathbb{Q}(i)$ ...
2
votes
0answers
36 views

Is it true that $\mathbb{Z}[i]/m\mathbb{Z}[i]$ has exactly $\text{N}(m)$ elements? [duplicate]

As the question title suggests, is it true that $\mathbb{Z}[i]/m\mathbb{Z}[i]$ has exactly $\text{N}(m)$ elements?
1
vote
3answers
43 views

Solve the linear congruence

Solve the pair $x \equiv 5 \pmod{9}$ and $10x \equiv 6 \pmod{28}$. So this means, $10x \equiv 5 \pmod{9}$ and $10x \equiv 6 \pmod{28}$. So this has a unique solution $10x \equiv a \pmod{252}$ So ...
0
votes
0answers
22 views

How to find the base of this expression?

I need to determine the radix of the numbers for make this expression true 15 = 8 How I can do that?
1
vote
2answers
64 views

Is $\gcd(a,b) = \gcd(2a,b)$?

I am currently learning number theory and specifically greatest common divisors. I was reading a solution to the following problem: The numbers in the sequence $101,104,109,116,\ldots$ are of the ...
0
votes
2answers
43 views

Proving Fermat's Little Theorem with Lagrange

I know how to prove Fermat's little theorem using the binomial expansion and induction. How can I prove it using Lagrange's theorem? So I want to show $c^p\equiv c\pmod p$, i.e. $c^{p-1}\equiv 1\...
-3
votes
0answers
39 views

Any prime number $(p)$, in sequence $(p^n, p^n+1…)$. Each term in sequence is divisible only for previous terms? [on hold]

Any prime number $(p)$, in sequence $(p^n, p^{n+1}, p^{n+2},...)$. Each term in sequence is divisible only by previous terms? This is relevant or simple derivation?
0
votes
0answers
12 views

Can these bounds, for the deficiency $D(x)=2x-\sigma(x)$ of a deficient number $x>1$, be improved?

Let $\sigma=\sigma_{1}$ denote the classical sum-of-divisors function. Denote the deficiency of the deficient number $x>1$ by $D(x)=2x-\sigma(x)$. Since $x>1$ is deficient, we have $D(x) \geq ...
0
votes
0answers
16 views

Prove that the product of $n$ consecutive integers is divisible by $n!$ [duplicate]

Problem : Prove that the product of $n$ consectutive integers is divisible by $n!$. $n!\mid a(a+1)(a+2)...(a+n-1)$
1
vote
1answer
30 views

Proving $133|a^{18}-b^{18}$ if $\gcd(a,133)=\gcd(b,133)=1$.

If $\gcd(a,133)=\gcd(b,133)=1$ then prove that $133|a^{18}-b^{18}$. Using Fermat theorem: $a^{132} \equiv 1\mod\ 133$ and $b^{132} \equiv 1\mod\ 133$, so $a^{132} \equiv b^{132}\mod\ 133$. What ...
2
votes
2answers
46 views

Testing prime numbers with modified Fermat's Little Theorem

Is there a number $n$ such that: $6n-1$ is prime There exists a positive integer $r<3n-1$ such that $4^{r}\equiv1\pmod{6n-1}$
3
votes
1answer
34 views

Proof of XOR properties

I want to prove the following two properties of the Nim-sum/XOR operator $\oplus$ to better understand Nim games. For the position $n = a_1 \oplus a_2 \oplus a_3 \oplus \cdots \oplus a_k = 0$, ...
0
votes
4answers
82 views

Dividing 100 pens among 5 children, everyone gets an odd number of pens: possible?

So I want to divide 100 pens among 5 children in a way that each of them gets an odd number of pens. I think it's not possible but what is the answer and why? Tag's may be wrong, please feel free to ...
7
votes
5answers
195 views

Disprove that “if $p$ is a prime number, then $2^p-1$ is also a prime number”?

We can see manually that $2^p-1$ is not prime. As $2047$ is not a prime. $2^{11} = 2048$. But I'm unable to figure out a formal way of disproving the statement.
0
votes
2answers
54 views

$n$th root of unity - why does polynomial $x^n-1$ factor as $(x-1)(x-\zeta)(x-\zeta^2)\cdots(x-\zeta^{n-1})$?

$n$th root of unity - why does polynomial $x^n-1$ factor as $(x-1)(x-\zeta)(x-\zeta^2)...(x-\zeta^{n-1})$? I am specifically working on the case of the $7$th root of unity. I know that $x^7-1$ will ...
2
votes
1answer
43 views

Norm of Gaussian integers: solutions to $N(a) = k$ for $k \in \mathbb{N}$ and $a$ a Guassian integer

I have two questions. Which integers are equal to the norm of some Gaussian integer? In general, how many solutions does$$\text{N}(a) = k$$have for a given $k \in \mathbb{Z}$? I am investigating the ...
1
vote
3answers
35 views

Let $\{a_1,a_2,\ldots,a_k\}$ be a set of integers and let $m=\text{lcm}(a_1,\ldots,a_k)$ Prove that if $a_1|n, a_2|n,\ldots$ and $a_k|n$ then $m|n$

Let $\{a_1,a_2,\ldots,a_k\}$ be a set of integers and let $m=\text{lcm}(a_1,\ldots ,a_k)$ What I am trying to prove is that if $a_1|n, a_2|n,\ldots, a_k|n$ then $m|n$. I understand that $m$ is the ...