20210826, 15:54  #12 
Feb 2017
Nowhere
2^{10}×5 Posts 
Yup.
Last fiddled with by Dr Sardonicus on 20210826 at 15:56 
20211120, 08:26  #13 
Aug 2020
79*6581e4;3*2539e3
2·11·19 Posts 
Another problem came up. The exercises deal with showing that a^x is congruent to 1 (or a) mod c, where c is a composite number:
a^21 == a (mod 15) for all a This is not a problem yet, but what I'm struggling with is if the composite has the square of a prime, such as: a^6 == 1 (mod 168) for all a where gcd(a,42)=1. 168 = 3*7*8 so it has to be shown that a^6 == 1 (mod 3), (mod 7), (mod 8). Mod 3 and 7 is no problem, but what about mod 8? 8 is not prime, so Fermat's little theorem cannot be applied. I noticed that apparently , but have no proof for it and I doubt they want that as solution as it wasn't discussed prior. I could prove it by the fact that all odd numbers squared are == 1 (mod 8), so (a^3)^2 is as well, but that only works for mod 8. Also, a later question is: a^4 = 1 (mod 60) for all a where gcd(a,30)=1. So (mod 4=2^2) comes into it. Last fiddled with by bur on 20211120 at 08:28 
20211120, 11:42  #14 
Dec 2012
The Netherlands
2×3×293 Posts 
The square of every odd number is congruent to 1 (mod 8).

20211120, 13:51  #15 
Feb 2017
Nowhere
5120_{10} Posts 
You could simply check a^2 (mod 8) for all four possible cases of a (mod 8). Then a^6 = (a^2)^3.
Note that knowing a^2 (mod 8) means you know a^2 (mod 4). 
20211120, 16:37  #16  
"Robert Gerbicz"
Oct 2005
Hungary
2×3×11×23 Posts 
Quote:
Let lambda(n)=lcm(,eulerphi(p[i]^e[i],) for n=prod(p[i]^e[i]) but if p=2 and e>2 then you can gain an additional factor of 2 on that place writing eulerphi(2^e)/2. And this is the best possible/smallest exponent what you can write for that a^lambda(n)==1 mod n for every gcd(a,n)=1. For example in your case n=2^3*3*7 and lambda(n)=lcm(2,2,6)=6 ps. maybe in maths you're using the unmodified lcm() when p=2 and e>2, the ugly case here is due to the fact that there is no primitive root mod 2^e if e>2.The proof of the best exponent is easy: just use that there is a primitive root mod m iff m=1,2,4,p^e or 2*p^e when p is an odd prime. 

20211121, 05:54  #17  
Aug 2020
79*6581e4;3*2539e3
110100010_{2} Posts 
I know, I wrote just that... ;)
Quote:
Quote:
So I assume they were after answers specific to that problem i.e. divisibility of of squares by 8 and 4. Thanks for your help everyone. 

20211126, 14:32  #18 
Aug 2020
79*6581e4;3*2539e3
418_{10} Posts 
And another one:
Show that It probably shouldn't use Wilson's theorem since that only comes in the next section in the book. I tried to write it as a fraction: All those factors cannot be reduced (mod p) since they smaller than p. And . I'd be thankful for a hint in the right direction. 
20211126, 18:12  #19 
Apr 2020
5·109 Posts 
It depends what you mean by "reduced". Try subtracting p from all the factors of the numerator, so p1 turns into 1, p2 into 2 etc, and see what that gives you.

20211126, 19:49  #20  
"Robert Gerbicz"
Oct 2005
Hungary
2×3×11×23 Posts 
Quote:
Freely use whatever theorems are in your head. Solutions without Wilson: About this problem (I know tex but not writing Latex here to save time): the precise problem: binomial(p1,k)==(1)^k mod p for 0<=k<p. the start was good, say if the answer is x then ((p1)*(p2)*...*(pk))/k!==x mod p multiple by k!, you need: (p1)*(p2)*...*(pk)==x*k! mod p, but in the left side: pi==(i) mod p for every i integer, so (1)*(2)*...*(k)==x*k! mod p k!*(1)^k==x*k! mod p, we can divide by k!, since k! is not divisible by p, so k! is relative prime to p. (1)^k==x mod p, what was needed. There is a one line solution here: (p1)*(p2)*...*(pk)/k!==(1)*(2)*...*(k)/k!==(1)^k*k!/k!==(1)^k mod p [you need somewhat more knowledge to understand this]. Last fiddled with by R. Gerbicz on 20211126 at 19:52 Reason: typo 

20211127, 15:16  #21 
Feb 2017
Nowhere
2^{10}·5 Posts 
Clearly binomial(p1,0) = 1 = (1)^0, so it's true for k = 0. Simplify the ratio binomial(p1,k+1)/binomial(p1,k) [you wind up with one linear term in the numerator and one in the denominator]. Check that the numerator and denominator are nonzero for k = 0 to p2, and are equal and opposite (mod p).

20211127, 16:10  #22  
"Robert Gerbicz"
Oct 2005
Hungary
2×3×11×23 Posts 
Quote:
The k=0 case is trivial, so assume that 0<k<p, it is known: binomial(p1,k1)+binomial(p1,k)=binomial(p,k) [for here you don't need that p is prime] furthermore: k*binomial(p,k)=p*binomial(p1,k1) is also true, here the right side is divisible by p, so the left side also, but 0<k<p, hence binomial(p,k) is divisible by p. From this binomial(p1,k)==binomial(p1,k1)==...==(1)^k*binomial(p1,0)==(1)^k mod p, what we needed. 

Thread Tools  
Similar Threads  
Thread  Thread Starter  Forum  Replies  Last Post 
k*b^n+/c where b is an integer greater than 2 and c is an integer from 1 to b1  jasong  Miscellaneous Math  5  20160424 03:40 
Sum of reciprocals of prime ktuplets  mart_r  Math  10  20090405 07:29 
Always an integer.  mfgoode  Puzzles  18  20070713 18:03 
Sum of all integer digits of all primes between 1 an n  AntonVrba  Math  2  20060920 17:20 
Primes for a mersenne integer DWT FNT  gbvalor  Math  1  20030908 16:05 