computabilityandcomplexity-資料下載頁
2025-07-15 18:12本頁面
【正文】 are present: 1 is a nonwitness of the first type, and 1 is a nonwitness of the second type Computability and Complexity 2712 Let d be a nonwitness of the second type such that the –1 appears in the largest position in the sequence Let and 12 ??? jsd 112 ??? jsdSince n is posite, n = qr for some coprime q and r Note that )(m od11)(m od11rq??)( m o d11)( m o d11rq??????and By the Chinese Reminder Theorem, there is t such that )(m o d1)(m o drtqdt?? therefore )( m o d1)( m o d122rtqtjjss?????Hence t is a witness, because but )( m o d12 pt js ??? )( m o d112 pt js ???Computability and Complexity 2713 Now, for every nonwitness a we set a180。 = a t ? a180。 is a witness, because and )( m o d12 pa js ???)( m o d1)()39。( 222 ptata jjj sss ????? ??? but )( m o d1)()39。( 111 222 ptata jjj sss ??? ??? ???? if then 21 aa ? 21 39。39。 aa ?Assume the contrary )( m o d39。39。 21 paa ?)( m o d21 ptata ?Then, since we have )( m o d112 pt js ??? )( m o d112 1 ptt js ???? ?22121121 11 aattatta jj ss ??????? ???? ??Finally, we have
環(huán)評公示相關(guān)推薦
鄂ICP備17016276號-1